J. Ellert

Practical and Space-Efficient LZ77 and LZ Pre-Compression via String Synchronizing Sets

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 bo...