On the Approximation Ratio of Ordered Parsings
Towards a Definitive Compressibility Measure for Repetitive Sequences
Tomasz Kociumaka, Gonzalo Navarro, and Nicola Prezza
While k-th order empirical entropy is an accepted measure of the compressibility of individual sequences on classical text collections, it fails to capture
the compressibility of repetitive sequences.
Lacking a clear and usable measure to capture the latter, ad-hoc measures like
the size z of the Lempel--Ziv parse are frequently used to estimate it.
The size b ≤ z 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 symbol appends.
Recently, a more principled measure, the size γ of the smallest
string attractor, was introduced.
The measure γ ≤ b lower bounds all the previous relevant ones,
while length-n strings can be represented and efficiently indexed within
space O(γ log(n/γ)), which also upper bounds most measures.
Although γ is arguably a better measure of repetitiveness than
b, it is also NP-complete to compute and not monotone, and it is unknown
if one can always represent a string in o(γ log n) space.
In this paper we study an even smaller measure, δ ≤ γ, which
can be computed in linear time, is monotone, and allows encoding every string
in O(δ log (n/δ)) space because z =
O(δ log (n/δ)). We show that δ better captures the
compressibility of repetitive strings. Concretely, we show that (1)
δ can be strictly smaller than γ, by up to a logarithmic
factor; (2) there are string families needing
Omega(δ log (n/δ)) space to be encoded, so this space is
optimal for every n and δ; (3) one can build run-length
context-free grammars of size O(δ log (n/δ)), whereas the
smallest (non-run-length) grammar can be up to Theta(log n / log log
times larger; and (4) within O(δ log (n/δ)) 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 σ of the string, showing that
Theta(δ log ((n log σ) / (δ log n))) space is necessary and sufficient to represent the string and to provide access, fingerprinting, and pattern searches on it.