conference · 2009
On the Use of Suffix Arrays for Memory-Efficient Lempel-Ziv Data Compression
See where this sits in the topic map →Summary AI-generated
- TL;DR
- This paper explores the use of suffix arrays to make Lempel-Ziv text compression algorithms more memory-efficient.
- Problem
- Traditional text compression algorithms like LZ77 and LZSS rely on binary search trees or suffix trees to speed up searches, but these data structures come at the cost of high memory usage.
- Method
- The research investigates replacing traditional data structures with a suffix array—a simpler, more compact array of integers that stores the lexicographic order of string suffixes to perform sub-string searches.
- Results
- Not specified in the abstract.
- Contributions
- Not specified in the abstract.
- Limitations
- Not specified in the abstract.
- Takeaways
- Suffix arrays offer a much more memory-efficient way to hold the information needed for string searching in LZ77 and LZSS compression algorithms.
- Applications
- Data compression systems using LZ77 or LZSS algorithms.
- Topics
- Suffix Arrays; Lempel-Ziv Data Compression; Text Compression
- For industry
- Not specified in the abstract.
- Why it matters
- Not specified in the abstract.
Abstract
The Lempel-Ziv 77 (LZ77) and LZ-Storer-Szymanski (LZSS) text compression algorithms use a sliding window over the sequence of symbols, with two sub-windows: the dictionary (symbols already encoded) and the look-ahead-buffer (LAB) (symbols not yet encoded). Binary search trees and suffix trees (ST) have been used to speedup the search of the LAB over the dictionary, at the expense of high memory usage [1]. A suffix array (SA) is a simpler, more compact data structure which uses (much) less memory [2,3] to hold the same information. The SA for a length m string is an array of integers ([1], ...[k], ...a[m]) that stores the lexicographic order of suffix k of the string; sub-string searching, as used in LZ77/LZSS, is done by searching the SA.