Efficient text compression method speeds up and cuts memory use
Practical and Space-Efficient LZ77 and LZ Pre-Compression via String Synchronizing Sets
Data Structures and Algorithms
Summary
Compressing text by finding repeated phrases quickly and with little memory is a challenge. The authors improved a recent method that cuts memory use and speeds up compression by replacing impractical components. Their new implementation runs much faster and uses less memory than older approaches, even on many computer cores. This helps prepare texts for further compression efficiently without losing quality.
What this means in practice
- •For software engineers: Reduce memory usage and speed up data compression tools by integrating this efficient LZ77 factorization approach.
- •For data center operators: Improve throughput and lower memory footprint of text compression in large-scale storage systems with the new precompression technique.
Authors
Jonas Ellert, Lukas Nalbach
Abstract
The Lempel-Ziv (LZ77) factorization decomposes a text into the least possible number $z$ of phrases that each refer to an earlier occurrence. It is this phrase count, rather than the encoded size, that governs the size of LZ-based compressed indexes, and computing a factorization with few phrases is a time and space bottleneck in their construction. In practice, computing LZ77 quickly has so far required building a suffix array. Ellert [SPIRE 2023] gave algorithms that compute the exact LZ77 factorization, and a 3-approximation of it, in sublinear working space. They have remained unimplemented, because two of their components resist a direct implementation: a lookup table that degenerates to patterns of length at most two for realistic inputs, and an orthogonal range reporting data structure that is impractical. We replace both, fine-tune every remaining stage, and obtain the first practical implementation, which runs in space close to the text rather than to the suffix array. On one thread, our 3-approximation factorizes 12-19x faster than the classical LPF algorithm while using 14x less memory; on 32 threads, even our exact algorithm is 1.4--2.9x faster than parallel LPF, at 9x less memory. In practice the approximation ratio stays far below 3. As a side result, passing only its perfect phrases to a downstream compressor yields a precompressor that is on par with the state of the art [Dinklage, SEA 2026] in compression ratio, and better in memory consumption and parallel throughput.