Sensitivity of string compressors and repetitiveness measures

DOI10.1016/J.IC.2022.104999MaRDI QIDQ2687989zbMATH OpenOpenAlexFDO

Authors Tooru Akagi, Mitsuru Funakoshi, Shunsuke Inenaga

Publication date 7 March 2023

Published in Information and Computation (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

bidirectional schemeedit operationsgrammar compressionLempel-Ziv factorizationslossless data compressionrun-length BWTsensitivitystring attractorssubstring complexity

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42) Algorithms on strings (68W32)

Abstract: The sensitivity of a string compression algorithm $C$ asks how much the output size $C(T)$ for an input string $T$ can increase when a single character edit operation is performed on $T$. This notion enables one to measure the robustness of compression algorithms in terms of errors and/or dynamic changes occurring in the input string. In this paper, we analyze the worst-case multiplicative sensitivity of string compression algorithms, which is defined by $ma{x}_{TinSigm{a}^n}C(T^{\prime })/C(T):ed(T,T^{\prime })=1$, where $ed(T,T^{\prime })$ denotes the edit distance between $T$ and $T^{\prime }$. For the most common versions of the Lempel-Ziv 77 compressors, we prove that the worst-case multiplicative sensitivity is upper bounded by a small constant, and give matching lower bounds. We generalize these results to the smallest bidirectional scheme $b$. In addition, we show that the sensitivity of a grammar-based compressor called GCIS is also a small constant. Further, we extend the notion of the worst-case sensitivity to string repetitiveness measures such as the smallest string attractor size $gamma$ and the substring complexity $delta$, and show that the worst-case sensitivity of $delta$ is also a small constant. These results contrast with the previously known related results such that the size $z_{m78}$ of the Lempel-Ziv 78 factorization can increase by a factor of $Omega(n^{1/4})$ [Lagarde and Perifel, 2018], and the number $r$ of runs in the Burrows-Wheeler transform can increase by a factor of $Omega(logn)$ [Giuliani et al., 2021] when a character is prepended to an input string of length $n$. By applying our sensitivity bounds of $delta$ or the smallest grammar to known results (c.f. [Navarro, 2021]), some non-trivial upper bounds for the sensitivities of important string compressors and repetitiveness measures including $gamma$, $r$, LZ-End, RePair, LongestMatch, and AVL-grammar are derived.

Recommendations

• Sublinear algorithms for approximating string compressibility
• Compression of Low Entropy Strings with Lempel--Ziv Algorithms
• Substring compression problems
• String matching in Lempel-Ziv compressed strings
• At the roots of dictionary compression: string attractors

Cites work

• A \textit{really} simple approximation of smallest grammar
• A combinatorial view on string attractors
• A universal algorithm for sequential data compression
• An LMS-based grammar self-index with local consistency properties
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• At the roots of dictionary compression: string attractors
• Block trees
• Complete inverted files for efficient text retrieval and analysis
• Compression of individual sequences via variable-rate coding
• Computing all distinct squares in linear time for integer alphabets
• Data compression via textual substitution
• Document listing on repetitive collections with guaranteed performance
• Dynamic index and LZ factorization in compressed space
• Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform. I. Without context models
• ESP-index: a compressed index based on edit-sensitive parsing
• Fully functional suffix trees and optimal text searching in BWT-runs bounded space
• Grammar index by induced suffix sorting
• Grammar-based codes: a new class of universal lossless source codes
• scientific article; zbMATH DE number 1149447 (Why is no real title available?)
• scientific article; zbMATH DE number 6850408 (Why is no real title available?)
• scientific article; zbMATH DE number 7696007 (Why is no real title available?)
• Indexing text using the Ziv--Lempel trie
• Lempel-Ziv compressed structures for document retrieval
• Lempel-Ziv: a ``one-bit catastrophe but not a tragedy
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Longest common extensions with recompression
• LZ77 factorisation of trees
• Novel results on the number of runs of the Burrows-Wheeler-transform
• On compressing and indexing repetitive sequences
• On stricter reachable repetitiveness measures
• Optimal rank and select queries on dictionary-compressed text
• Optimal-Time Dictionary-Compressed Indexes
• Refining the \(r\)-index
• Relative Lempel-Ziv compression of genomes for large-scale storage and retrieval
• Representing the suffix tree with the CDAWG
• Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections
• String attractors: verification and optimization
• The Smallest Grammar Problem
• Time-space trade-offs for Lempel-Ziv compressed indexing
• Top Tree Compression of Tries.
• Towards a definitive measure of repetitiveness
• Two Efficient Algorithms for Linear Time Suffix Array Construction
• Tying up the loose ends in fully LZW-compressed pattern matching
• Universal compressed text indexing

Cited in

(15)

• Towards a definitive measure of repetitiveness
• Bit catastrophes for the Burrows-Wheeler transform
• Substring complexities on run-length compressed strings
• On Sensitivity of Compact Directed Acyclic Word Graphs
• Iterated straight-line programs
• On the number of equal-letter runs of the bijective Burrows-Wheeler transform
• Maintaining the size of LZ77 on semi-dynamic strings
• The 2-attractor problem is NP-complete
• Bit catastrophes for the Burrows-Wheeler transform
• Generalized straight-line programs
• Tight bounds for the sensitivity of CDAWGs with left-end edits
• Differentially private compression and the sensitivity of LZ77
• Edit and alphabet-ordering sensitivity of lex-parse
• Morphisms and BWT-run sensitivity
• Smallest suffixient sets: effectiveness, resilience, and calculation

This page was built for publication: Sensitivity of string compressors and repetitiveness measures

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