LEMPEL-ZIV SLIDING WINDOW UPDATE WITH SUFFIX ARRAYS
See where this sits in the topic map →Summary AI-generated
- TL;DR
- This research introduces a more memory-efficient suffix array-based approach for Lempel-Ziv (LZ) 77 sliding window data compression.
- Problem
- Traditional LZ77 encoders use heavy data structures like hash tables, binary search trees, and suffix trees to speed up repeated substring searches, which leads to high memory usage.
- Method
- The authors propose an efficient algorithm to update the sliding window as each token is produced, toggling between two suffix arrays on consecutive tokens.
- Results
- When tested on a large set of benchmark files, the proposed suffix array-based encoder required less memory than conventional tree-based encoders and, in some compression settings, proved to be faster.
- Contributions
- A new, efficient algorithm for updating the sliding window using suffix arrays to represent the dictionary and handle LZ77 decomposition.
- Limitations
- Not specified in the abstract.
- Takeaways
- Suffix arrays can replace traditional tree structures in LZ77 compressors to reduce memory consumption while remaining competitive in speed.
- Applications
- Universal lossless data compression using sliding window dictionary-based algorithms.
- Topics
- Data compression, Lempel-Ziv 77, suffix arrays, sliding window algorithms
- For industry
- Not specified in the abstract.
- Why it matters
- Not specified in the abstract.
Abstract
The sliding window dictionary-based algorithms of the Lempel-Ziv (LZ) 77 family are widely used for universal lossless data compression. The encoding component of these algorithms performs repeated substring search. Data structures, such as hash tables, binary search trees, and suffix trees have been used to speedup these searches, at the expense of memory usage. Previous work has shown how suffix arrays (SA) can be used for dictionary representation and LZ77 decomposition. In this paper, we improve over that work by proposing a new efficient algorithm to update the sliding window each time a token is produced at the output. The proposed algorithm toggles between two SA on consecutive tokens. The resulting SA-based encoder requires less memory than the conventional tree-based encoders. In comparing our SA-based technique against tree-based encoders, on a large set of benchmark files, we find that, in some compression settings, our encoder is also faster than tree-based encoders.