Summary
The paper finds that one popular data compression method, called LZ77, can compress some data much more efficiently than two other methods called LZ-End and grammar compression. Specifically, the difference in how compact the results are can grow like the logarithm of the input size, meaning the gap can be significantly large as data gets bigger. The authors establish this by proving a theoretical limit, showing these methods are not equally powerful for all inputs.
What this means in practice
- •For compression algorithm designers: Guide design choices by understanding limits where LZ77 outperform LZ-End and grammar compression on some inputs.
- •For storage system engineers: Identify when to prefer LZ77 compression to achieve better space efficiency for large data sets.
A theory result. No direct application yet.
Authors
Philip Bille, Inge Li Gørtz, Rikke Jessen, Jingxun Li, Simon Rumle Tarnow, Renfei Zhou
Abstract
We show that there is a logarithmic separation between LZ77 and LZ-End, and between LZ77 and grammar compression.