Answers are grounded in this paper and cite their sources.
While the <tex-math notation="LaTeX">k </tex-math> th order empirical entropy is an accepted measure of the compressibility of individual sequences on classical text collections, it is useful only for small values of <tex-math notation="LaTeX">k </tex-math> and thus fails to capture the compressibility of repetitive sequences. In the absence of an established way of quantifying the latter, ad-hoc measures like the size <tex-math notation="LaTeX">z </tex-math> of the Lempel–Ziv parse are frequently used to estimate repetitiveness. The size <tex-math notation="LaTeX">b ≤ z </tex-math> of the smallest bidirectional macro scheme captures better what can be achieved via copy-paste processes, though it is NP-complete to compute, and it is not monotone upon appending symbols. Recently, a more principled measure, the size <tex-math notation="LaTeX">γ </tex-math> of the smallest string attractor , was introduced. The measure <tex-math notation="LaTeX">γ ≤ b </tex-math> lower-bounds all the previous relevant ones, while length- <tex-math notation="LaTeX">n </tex-math> strings can be represented and efficiently indexed within space <tex-math notation="LaTeX">O(γ log n/γ ) </tex-math> , which also upper-bounds many measures, including <tex-math notation="LaTeX">z </tex-math> . Although <tex-math notation="LaTeX">γ </tex-math> is arguably a better measure of repetitiveness than <tex-math notation="LaTeX">b </tex-math> , it is also NP-complete to compute and not monotone, and it is unknown if one can represent all strings in <tex-math notation="LaTeX">o(γ log n) </tex-math> space. In this paper, we study an even smaller measure, <tex-math notation="LaTeX">δ ≤ γ </tex-math> , which can be computed in linear time, is monotone, and allows encoding every string in <tex-math notation="LaTeX">O(δ log n/δ ) </tex-math> space because <tex-math notation="LaTeX">z = O(δ log n/δ ) </tex-math> . We argue that <tex-math notation="LaTeX">δ </tex-math> better captures the compressibility of repetitive strings. Concretely, we show that (1) <tex-math notation="LaTeX">δ </tex-math> can be strictly smaller than <tex-math notation="LaTeX">γ </tex-math> , by up to a logarithmic factor; (2) there are string families needing <tex-math notation="LaTeX">Ω (δ log n/δ ) </tex-math> space to be encoded, so this space is optimal for every <tex-math notation="LaTeX">n </tex-math> and <tex-math notation="LaTeX">δ </tex-math> ; (3) one can build run-length context-free grammars of size <tex-math notation="LaTeX">O(δ log n/δ ) </tex-math> , whereas the smallest (non-run-length) grammar can be up to <tex-math notation="LaTeX">Θ (log n/log log n) </tex-math> times larger; and (4) within <tex-math notation="LaTeX">O(δ log n/δ ) </tex-math> space, we can not only represent a string but also offer logarithmic-time access to its symbols, computation of substring fingerprints, and efficient indexed searches for pattern occurrences. We further refine the above results to account for the alphabet size <tex-math notation="LaTeX">σ </tex-math> of the string, showing that <tex-math notation="LaTeX">Θ (δ log nlog σ /δ log n) </tex-math> space is necessary and sufficient to represent the string and to efficiently support access, fingerprinting, and pattern matching queries.
No takes yet. Share an insight, caveat, or question.
Kociumaka et al. (2022) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: