SUFFIX ARRAYS - A Competitive Choice for Fast Lempel-Ziv Compressions
See where this sits in the topic map →Summary AI-generated
- TL;DR
- Lossless compression algorithms of the Lempel-Ziv (LZ) family are widely used across applications, but their encoders and decoders show high asymmetry, with encoders being much more demanding in time and memory.
- Problem
- LZ encoders are significantly more demanding in time and memory requirements compared to decoders.
- Method
- The authors explore using a simple data structure—the suffix array—to hold the dictionary of the LZ encoder, propose a corresponding search algorithm, and compare it with suffix tree-based LZ encoders.
- Results
- The compression ratios achieved using suffix arrays are roughly the same as those using suffix trees.
- Contributions
- Not specified in the abstract.
- Limitations
- Not specified in the abstract.
- Takeaways
- Suffix arrays offer a very interesting trade-off between time, memory, and compression ratio compared to suffix trees, featuring a fixed and much lower memory requirement that makes them preferable in certain compression scenarios.
- Applications
- Lossless data compression applications.
- Topics
- Lempel-Ziv, Lossless Data Compression, Suffix Arrays, Suffix Trees, String Matching
- For industry
- Not specified in the abstract.
- Why it matters
- Not specified in the abstract.
Abstract
Keywords: Lempel-Ziv, Lossless Data Compression, Suffix Arrays, Suffix Tre es, String Matching.Abstract: Lossless compression algorithms of the Lempel-Ziv (LZ) family are widely used in a variety of applications.The LZ encoder and decoder exhibit a high asymmetry, regarding time and memory requirements, with theformer being much more demanding. Several techniques have been used to speed up the encoding process;among them is the use of suffix trees. In this paper, we explore the use of a simple data structure, namedsuffix array , to hold the dictionary of the LZ encoder, and propose an algorithm to search the dictionary.A comparison with the suffix tree based LZ encoder is carried out, showin g that the compression ratios areroughly the same. The ammount of memory required by the suffix arra y is fixed, being much lower than thevariable memory requirements of the suffix tree encoder, which depen ds on the text to encode. We concludethat suffix arrays are a very interesting option regarding the tradeoff b etween time, memory, and compressionratio, when compared with suffix trees, that make them preferable in som e compression scenarios.