At the roots of dictionary compression: string attractors

DOI10.1145/3188745.3188814zbMath1418.68085arXiv1710.10964OpenAlexW2765521106WikidataQ130958555 ScholiaQ130958555MaRDI QIDQ5230341

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

zbMATH Keywords

compressed data structuresdictionary compression

Mathematics Subject Classification ID

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

Related Items (41)

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

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