At the roots of dictionary compression: string attractors

DOI10.1145/3188745.3188814zbMATH Open1418.68085arXiv1710.10964OpenAlexW2765521106WikidataQ130958555 ScholiaQ130958555MaRDI QIDQ5230341FDOQ5230341

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)

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.

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

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

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)

Cited In (41)

• On Sensitivity of Compact Directed Acyclic Word Graphs
• String Attractors of Fixed Points of k-Bonacci-Like Morphisms
• String attractors of episturmian sequences
• Novel results on the number of runs of the Burrows-Wheeler-transform
• Bidirectional Text Compression in External Memory
• Tight Upper Bounds on Distinct Maximal (Sub-)Repetitions in Highly Compressible Strings
• Block trees
• Comparison of LZ77-type parsings
• Title not available (Why is that?)
• A new class of searchable and provably highly compressible string transformations
• New string attractor-based complexities for infinite words
• 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
• 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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Sensitivity of string compressors and repetitiveness measures
• String attractors of some simple-parry automatic sequences
• Balancing run-length straight-line programs
• String Attractors for Factors of the Thue-Morse Word
• A combinatorial view on string attractors
• 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
• Random access in persistent strings and segment selection
• Dynamic index and LZ factorization in compressed space
• Near-optimal search time in \(\delta \)-optimal space, and vice versa

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)