Toward a Definitive Compressibility Measure for Repetitive Sequences

DOI10.1109/TIT.2022.3224382arXiv1910.02151OpenAlexW3125235775MaRDI QIDQ6153652FDOQ6153652

Authors: Tomasz Kociumaka, Gonzalo Navarro, Nicola Prezza 

Publication date: 19 March 2024

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: Unlike in statistical compression, where Shannon's entropy is a definitive lower bound, no such clear measure exists for the compressibility of repetitive sequences. Since statistical entropy does not capture repetitiveness, ad-hoc measures like the size $z$ of the Lempel--Ziv parse are frequently used to estimate it. The size $blez$ 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 monotonic upon symbol appends. Recently, a more principled measure, the size $gamma$ of the smallest string emph{attractor}, was introduced. The measure $gammaleb$ lower bounds all the previous relevant ones, yet length-$n$ strings can be represented and efficiently indexed within space $O(gammalogfracngamma)$, which also upper bounds most measures. While $gamma$ is certainly a better measure of repetitiveness than $b$, it is also NP-complete to compute and not monotonic, and it is unknown if one can always represent a string in $o(gammalogn)$ space. In this paper, we study an even smaller measure, $deltalegamma$, which can be computed in linear time, is monotonic, and allows encoding every string in $O(deltalogfracndelta)$ space because $z=O(deltalogfracndelta)$. 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(deltalogfracndelta)$ 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(deltalogfracndelta)$, whereas the smallest (non-run-length) grammar can be up to $Theta(logn/loglogn)$ times larger; and (4) within $O(deltalogfracndelta)$ space we can not only...

Full work available at URL: https://arxiv.org/abs/1910.02151

zbMATH Keywords

data compressionrepetitive sequencessubstring complexitystring attractorsLempel-Ziv parse

Mathematics Subject Classification ID

Information and communication theory, circuits (94-XX)

Cited In (9)

• New string attractor-based complexities for infinite words
• Internal pattern matching queries in a text and applications
• String attractors of some simple-parry automatic sequences
• Compressibility measures for two-dimensional data
• Frequency-constrained substring complexity
• Non-overlapping indexing in BWT-runs bounded space
• Iterated straight-line programs
• Space-efficient conversions from SLPs
• Near-optimal search time in \(\delta \)-optimal space, and vice versa

This page was built for publication: Toward a Definitive Compressibility Measure for Repetitive Sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6153652)