@inproceedings{4d38df468ea346a18ad12256cb9da2b1,
title = "Lempel-Ziv Compression in a Sliding Window",
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.",
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)",
author = "Philip Bille and Cording, {Patrick Hagge} and Johannes Fischer and G{\o}rtz, {Inge Li}",
year = "2017",
doi = "10.4230/LIPIcs.CPM.2017.15",
language = "English",
isbn = "9783959770392",
series = "Leibniz International Proceedings in Informatics",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
pages = "15",
booktitle = "Proceedings of 28th Annual Symposium on Combinatorial Pattern Matching",
note = "28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017 ; Conference date: 04-07-2017 Through 06-07-2017",
}