On the Adaptive Covering Complexity of Strings: Unifying Relative and Self-Referential Compression
Overview & Synopsis
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.
arxiv.org)
← / → for pages • + / - for zoom • 0 to fit width
Powered by Mozilla PDF.js v3.11
Document Information
| Document Title | On the Adaptive Covering Complexity of Strings: Unifying Relative and Self-Referential Compression |
|---|---|
| Author / Organization | Pierre-Fran{\c c}ois Marteau |
| Subject & Discipline | cs.IT |
| Categories | Science & Mathematics |
| Publication Year | 2026 |
| License / Rights | arXiv Open Access / Creative Commons |
| Resource Verification | Listed PDF (Verification Pending) |
| Original Host Website |
arXiv
(arxiv.org)
|
| File Format | application/pdf (Portable Document Format) |
| Language | EN |
| Catalog ID | DOC-273998 |
| Original Source Link | Visit Source Page on arxiv.org » |