Grammar compression algorithm has growing worst-case inefficiency
A Non-constant Lower Bound for Grammar-Based Compression with Greedy
Data Structures and AlgorithmsFormal Languages and Automata Theory
Summary
Compressing data by finding patterns and expressing them as rules is common, but figuring out how well certain methods perform is tricky. The authors show that a popular greedy method for grammar-based compression can sometimes perform increasingly worse compared to the best possible compression as the data size grows. This means that the efficiency of this method doesn’t just have a fixed worst case; it can get worse logarithmically with input size. They also used formal verification tools to prove their finding rigorously.
What this means in practice
- •For software engineers: Understand limits of greedy grammar compression when choosing compression algorithms for large textual data sets.
- •For data system architects: Avoid relying on greedy grammar compression for guaranteed near-optimal compression ratios in scalable storage systems.
A theory result. No direct application yet.
Authors
Danny Hucke
Abstract
We prove a lower bound of Ω(log n/ log log n) on the approximation ratio of the global grammar-based compression algorithm Greedy. To our knowledge, the previously best lower bound was a constant, and the existence of a nonconstant lower bound had remained open for more than twenty years. Our bound holds on an infinite family of words of length n, over alphabets of growing size, for every execution using left-to-right occurrence replacement and arbitrary tie-breaking. The lower bound is also formally verified in Lean 4.