Lempel-Ziv Compression in a Sliding Window

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2017

Documents

DOI

View graph of relations

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
StatePublished - 2017
Event28th Annual Symposium on Combinatorial Pattern Matching - Warsaw, Poland

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
CitationsWeb of Science® Times Cited: No match on DOI

    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)
Download as:
Download as PDF
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
Word

Download statistics

No data available

ID: 134976711