Toward a Definitive Compressibility Measure for Repetitive Sequences

DOI10.1109/TIT.2022.3224382MaRDI QIDQ6153652zbMATH OpenOpenAlexFDO

Authors Tomasz Kociumaka, Gonzalo Navarro, Nicola Prezza

Publication date 19 March 2024

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

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

zbMATH Keywords

data compressionLempel-Ziv parserepetitive sequencesstring attractorssubstring complexity

Mathematics Subject Classification ID

Information and communication theory, circuits (94-XX)

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...

Cited in

(26)

• Near-optimal search time in -optimal space, and vice versa
• Compressibility measures for two-dimensional data
• Non-overlapping indexing in BWT-runs bounded space
• Frequency-constrained substring complexity
• Iterated straight-line programs
• Space-efficient conversions from SLPs
• 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
• Exploiting new properties of string net frequency for efficient computation
• Non-overlapping indexing in BWT-runs bounded space
• Substring complexity in sublinear space
• Repetitiveness measures based on string morphisms
• Bit catastrophes for the Burrows-Wheeler transform
• Generalized straight-line programs
• Computing MEMs and relatives on repetitive text collections
• Tight bounds for the sensitivity of CDAWGs with left-end edits
• Faster and simpler online computation of string net frequency
• LZ78 substring compression in compressed space
• Generalization of repetitiveness measures for two-dimensional strings
• Logarithmic-time internal pattern matching queries in compressed and dynamic texts
• Two-dimensional longest common extension queries in compact space
• Counting on general run-length grammars
• Pattern matching on run-length grammar-compressed strings in linear time
• On the compressiveness of the Burrows-Wheeler transform
• Repetition aware text indexing for matching patterns with wildcards

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)