Lempel-Ziv Compression in a Sliding Window

Philip Bille, Patrick Hagge Cording, Johannes Fischer, Inge Li Gørtz

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

844 Downloads (Pure)

Abstract

We present new algorithms for the sliding window Lempel-Ziv (LZ77) problem and the approximate rightmost LZ77 parsing problem. Our main result is a new and surprisingly simple algorithm that computes the sliding window LZ77 parse in O(w) space and either O(n) expected time or O(n log log w + z log logσ) deterministic time. Here, w is the window size, n is the size of the input string, z is the number of phrases in the parse, and σ is the size of the alphabet. This matches the space and time bounds of previous results while removing constant size restrictions on the alphabet size. To achieve our result, we combine a simple modification and augmentation of the suffix tree with periodicity properties of sliding windows. We also apply this new technique to obtain an algorithm for the approximate rightmost LZ77 problem that uses O(n(log z + loglogn)) time and O(n) space and produces a (1 + ϵ)-approximation of the rightmost parsing (any constant ϵ > 0). While this does not improve the best known time-space trade-offs for exact rightmost parsing, our algorithm is significantly simpler and exposes a direct connection between sliding window parsing and the approximate rightmost matching problem.
Original languageEnglish
Title of host publicationProceedings of 28th Annual Symposium on Combinatorial Pattern Matching
Number of pages1
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date2017
Pages15
ISBN (Print)9783959770392
DOIs
Publication statusPublished - 2017
Event28th Annual Symposium on Combinatorial Pattern Matching - University of Warsaw Library, Warsaw, Poland
Duration: 4 Jul 20176 Jul 2017

Conference

Conference28th Annual Symposium on Combinatorial Pattern Matching
LocationUniversity of Warsaw Library
CountryPoland
CityWarsaw
Period04/07/201706/07/2017
SeriesLeibniz International Proceedings in Informatics
Volume78
ISSN1868-8969

Keywords

  • Information and Communication Theory
  • Data Processing
  • Applied Mathematics
  • Social Sciences
  • Lempel-Ziv parsing
  • Rightmost matching
  • Sliding window
  • Approximation algorithms
  • Decoding
  • Economic and social effects
  • Pattern matching
  • Matching problems
  • Parsing problems
  • Periodicity property
  • SIMPLE algorithm
  • Simple modifications
  • Sliding Window
  • Communication channels (information theory)

Cite this