|
Abstract |
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 gamma of the smallest string attractor, was introduced. The measure gamma < b lower bounds all the previous relevant ones, while length-n strings can be represented and efficiently indexed within space O(gamma log(n/gamma)), which also upper bounds most measures. Although gamma 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(gamma log n) space. In this paper we study an even smaller measure, delta < gamma, which can be computed in linear time, is monotone, and allows encoding every string in O(delta log (n/delta)) space because z = O(delta log (n/delta)). We show that delta better captures the compressibility of repetitive strings. Concretely, we show that (1) delta can be strictly smaller than gamma, by up to a logarithmic factor; (2) there are string families needing Omega(delta log (n/delta)) space to be encoded, so this space is optimal for every n and delta; (3) one can build run-length context-free grammars of size O(delta log (n/delta)), whereas the smallest (non-run-length) grammar can be up to Theta(log n / log log n) times larger; and (4) within O(delta log (n/delta)) 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 sigma of the string, showing that Theta(delta log ((n log sigma) / (delta log n))) space is necessary and sufficient to represent the string and to provide access, fingerprinting, and pattern searches on it. |
