Lempel-Ziv Compression in a Sliding Window

Philip Bille, Patrick Hagge Cording, Johannes Fischer & Inge Li Gørtz
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...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.