At the roots of dictionary compression: string attractors

DOI10.1145/3188745.3188814MaRDI QIDQ5230341zbMATH OpenOpenAlexWikidataFDO

Authors Dominik Kempa, Nicola Prezza

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.10964, https://orbit.dtu.dk/en/publications/0d148272-07ca-47eb-b645-97fe1aab318d

zbMATH Keywords

compressed data structuresdictionary compression

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Abstract: A well-known fact in the field of lossless text compression is that high-order entropy is a weak model when the input contains long repetitions. Motivated by this, decades of research have generated myriads of so-called dictionary compressors: algorithms able to reduce the text's size by exploiting its repetitiveness. Lempel-Ziv 77 is one of the most successful and well-known tools of this kind, followed by straight-line programs, run-length Burrows-Wheeler transform, macro schemes, collage systems, and the compact directed acyclic word graph. In this paper, we show that these techniques are different solutions to the same, elegant, combinatorial problem: to find a small set of positions capturing all text's substrings. We call such a set a string attractor. We first show reductions between dictionary compressors and string attractors. This gives the approximation ratios of dictionary compressors with respect to the smallest string attractor and uncovers new relations between the output sizes of different compressors. We show that the $k$-attractor problem: deciding whether a text has a size-$t$ set of positions capturing substrings of length at most $k$, is NP-complete for $kgeq3$. We provide several approximation techniques for the smallest $k$-attractor, show that the problem is APX-complete for constant $k$, and give strong inapproximability results. To conclude, we provide matching lower and upper bounds for the random access problem on string attractors. The upper bound is proved by showing a data structure supporting queries in optimal time. Our data structure is universal: by our reductions to string attractors, it supports random access on any dictionary-compression scheme. In particular, it matches the lower bound also on LZ77, straight-line programs, collage systems, and macro schemes, and therefore closes (at once) the random access problem for all these compressors.

Recommendations

• Compressed string dictionaries via data-aware subtrie compaction
• Sublinear algorithms for approximating string compressibility
• Sublinear Algorithms for Approximating String Compressibility
• Compact \(q\)-gram profiling of compressed strings
• Compressed string-matching in standard Sturmian words
• A new class of searchable and provably highly compressible string transformations
• Compression of Low Entropy Strings with Lempel--Ziv Algorithms
• Compressed data structures for strings. On searching and extracting strings from compressed textual data

Cited in

(41)

• Random access in persistent strings and segment selection
• Near-optimal search time in \(\delta \)-optimal space, and vice versa
• On Sensitivity of Compact Directed Acyclic Word Graphs
• Novel results on the number of runs of the Burrows-Wheeler-transform
• String Attractors of Fixed Points of k-Bonacci-Like Morphisms
• String attractors of episturmian sequences
• Bidirectional Text Compression in External Memory
• Block trees
• Tight Upper Bounds on Distinct Maximal (Sub-)Repetitions in Highly Compressible Strings
• Comparison of LZ77-type parsings
• scientific article; zbMATH DE number 7651154 (Why is no real title available?)
• A new class of searchable and provably highly compressible string transformations
• A separation of \(\gamma\) and \(b\) via Thue-Morse words
• An LMS-based grammar self-index with local consistency properties
• On stricter reachable repetitiveness measures
• New string attractor-based complexities for infinite words
• Lempel-Ziv-like parsing in small space
• LZRR: LZ77 parsing with right reference
• Logarithmic equal-letter runs for BWT of purely morphic words
• Linear-size suffix tries and linear-size CDAWGs simplified and improved
• scientific article; zbMATH DE number 7378722 (Why is no real title available?)
• On the approximation ratio of LZ-end to LZ77
• Near-optimal search time in \(\delta \)-optimal space
• Optimal rank and select queries on dictionary-compressed text
• A compressed dynamic self-index for highly repetitive text collections
• Substring complexities on run-length compressed strings
• Sensitivity of string compressors and repetitiveness measures
• scientific article; zbMATH DE number 7765406 (Why is no real title available?)
• String attractors of some simple-parry automatic sequences
• A combinatorial view on string attractors
• Balancing run-length straight-line programs
• String Attractors for Factors of the Thue-Morse Word
• Universal compressed text indexing
• String attractors and infinite words
• Compressibility measures for two-dimensional data
• Computing all-vs-all MEMs in grammar-compressed text
• Data structures for SMEM-finding in the PBWT
• Sublinear time Lempel-Ziv (LZ77) factorization
• Iterated straight-line programs
• Space-efficient conversions from SLPs
• Dynamic index and LZ factorization in compressed space

This page was built for publication: At the roots of dictionary compression: string attractors

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