License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2017.15
URN: urn:nbn:de:0030-drops-73316
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7331/
Bille, Philip ;
Cording, Patrick Hagge ;
Fischer, Johannes ;
Gørtz, Inge Li
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 s) 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 s 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 + log log n)) time and O(n) space and produces a (1+e)-approximation of the rightmost parsing (any constant e>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.
BibTeX - Entry
@InProceedings{bille_et_al:LIPIcs:2017:7331,
author = {Philip Bille and Patrick Hagge Cording and Johannes Fischer and Inge Li G\ortz},
title = {{Lempel-Ziv Compression in a Sliding Window}},
booktitle = {28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
pages = {15:1--15:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-039-2},
ISSN = {1868-8969},
year = {2017},
volume = {78},
editor = {Juha K{\"a}rkk{\"a}inen and Jakub Radoszewski and Wojciech Rytter},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7331},
URN = {urn:nbn:de:0030-drops-73316},
doi = {10.4230/LIPIcs.CPM.2017.15},
annote = {Keywords: Lempel-Ziv parsing, sliding window, rightmost matching}
}
Keywords: |
|
Lempel-Ziv parsing, sliding window, rightmost matching |
Collection: |
|
28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017) |
Issue Date: |
|
2017 |
Date of publication: |
|
30.06.2017 |