Time and Memory Efficient Lempel-Ziv Compression Using Suffix Arrays
See where this sits in the topic map →Summary AI-generated
- TL;DR
- This paper presents faster and more memory-efficient suffix-array-based algorithms for Lempel-Ziv 77 (LZ77) encoding and substring search.
- Problem
- LZ77-family compression algorithms are asymmetric, making encoders much more demanding in time and memory than decoders. While traditional data structures like hash tables and suffix trees allow fast searches, they do so at the expense of high memory usage.
- Method
- The authors propose faster suffix-array (SA) based algorithms for LZ77 encoding and substring search that maintain the low memory requirements characteristic of SA-based approaches.
- Results
- For certain compression settings across a large benchmark of files, these low-memory SA-based encoders outperform tree-based encoders in speed while preserving minimal memory usage.
- Contributions
- The paper introduces improved SA-based algorithms for LZ77 encoding and substring search that achieve both time and memory efficiency, offering a viable replacement for trees in established encoders like LZMA.
- Limitations
- Not specified in the abstract.
- Takeaways
- The proposed algorithms offer a compact text description for bag-of-words representations and a fast indexing mechanism to quickly locate word sets starting with a given symbol over a static dictionary, making them well-suited for text classification.
- Applications
- Universal lossless data compression and text classification.
- Topics
- Lempel-Ziv compression, suffix arrays, lossless compression, text classification, data structures
- For industry
- Not specified in the abstract.
- Why it matters
- Not specified in the abstract.
Abstract
The well-known dictionary-based algorithms of the Lempel-Ziv (LZ) 77 family are the basis of several universal lossless compression techniques. These algorithms are asymmetric regarding encoding/decoding time and memory requirements, with the former being much more demanding. In the past years, considerable attention has been devoted to the problem of finding efficient data structures to support these searches, aiming at optimizing the encoders in terms of speed and memory. Hash tables, binary search trees and suffix trees have been widely used for this purpose, as they allow fast search at the expense of memory. Some recent research has focused on suffix arrays (SA), due to their low memory requirements and linear construction algorithms. Previous work has shown how the LZ77 decomposition can be computed using a single SA or an SA with an auxiliary array with the longest common prefix information. The SA-based algorithms use less memory than the tree-based encoders, allocating the strictly necessary amount of memory, regardless of the contents of the text to search/encode. In this paper, we improve on previous work by proposing faster SA-based algorithms for LZ77 encoding and sub-string search, keeping their low memory requirements. For some compression settings, on a large set of benchmark files, our low-memory SA-based encoders are also faster than tree-based encoders. This provides time and memory efficient LZ77 encoding, being a possible replacement for trees on well known encoders like LZMA. Our algorithm is also suited for text classification, because it provides a compact way to describe text in a bag-of-words representation, as well as a fast indexing mechanism that allows to quickly find all the sets of words that start with a given symbol, over a static dictionary.