Logarithmic gap found between LZ77 and grammar compression methods

Logarithmic Separation between LZ77 and LZ-End and Grammar Compression

Information TheoryData Structures and Algorithms

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

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.