Adaptive covering complexity links static and self referencing compression
On the Adaptive Covering Complexity of Strings: Unifying Relative and Self-Referential Compression
Information Theory
Summary
Compressing data can be done by using a fixed dictionary of known pieces or by referencing parts of the data already processed. This paper introduces a way to measure compression complexity when combining both methods. The authors show that using self-reference improves compression but only up to a certain limit compared to dictionary-based methods. They also present efficient algorithms and theoretical bounds that unify two popular text compression techniques.
What this means in practice
- •For data compression engineers: Design compression algorithms that balance dictionary and self-reference methods to achieve near-optimal phrase counts with efficient parsing.
- •For network system designers: Optimize network data transfer by selecting compression schemes that minimize segments while allowing self-referential coding for better bandwidth use.
A theory result. No direct application yet.
Authors
Pierre-Fran{\c c}ois Marteau
Abstract
We introduce and study the adaptive covering complexity C adapt S (s), defined as the minimum number of contiguous factor blocks required to partition a string s when each block is either a factor of a fixed external dictionary S or a factor of the target's already decoded prefix. This hybrid admissibility model formalizes the structural interaction between static dictionary matching and dynamic nonoverlapping self-referencing. Our main theoretical result is the exact logarithmic law which is tight and proves that dynamic self-reference can reduce phrase count by at most an exponential factor over static dictionary covering alone. We establish structural equivalences showing that the measure bridges word-segmented Relative Lempel-Ziv and non-overlapping LZ77, and we prove exact preset-history LZ77 sandwich bounds. Furthermore, we establish the optimality of the longest-match greedy parse via an exchange lemma and present an optimal implementation based on dual suffix automata running in O(M + n) time and space for a constant alphabet. These analytical results are complemented by counting bounds, stationary-ergodic asymptotic invariance, a dictionaryselection NP-hardness result, and a concise empirical illustration.