Optimal-Time Dictionary-Compressed Indexes

DOI10.1145/3426473MaRDI QIDQ5028345zbMATH OpenOpenAlexFDO

Authors Anders Roy Christiansen, Mikko Berggren Ettienne, Tomasz Kociumaka, Nicola Prezza, Gonzalo Navarro

Publication date 8 February 2022

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

attractorscompressed text indexesgrammar compressionlocally consistent parsingrepetitive string collections

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Universal compressed text indexing
• Faster compressed dictionary matching
• Fast compressed self-indexes with deterministic linear-time construction
• Fast Compressed Self-Indexes with Deterministic Linear-Time Construction
• scientific article; zbMATH DE number 6850405

Cited in

(44)

• Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms.
• Time-space trade-offs for Lempel-Ziv compressed indexing
• Grammar index by induced suffix sorting
• An LMS-based grammar self-index with local consistency properties
• On the approximation ratio of LZ-end to LZ77
• On stricter reachable repetitiveness measures
• Logarithmic equal-letter runs for BWT of purely morphic words
• Compressing dictionary matching index via sparsification technique
• Compressed data structures: Dictionaries and data-aware measures
• Grammar-compressed indexes with logarithmic search time
• Sensitivity of string compressors and repetitiveness measures
• BOUNDED SIZE DICTIONARY COMPRESSION: RELAXING THE LRU DELETION HEURISTIC
• Constructing Efficient Dictionaries in Close to Sorting Time
• Optimal indexes for sparse bit vectors
• String attractors: verification and optimization
• Optimal rank and select queries on dictionary-compressed text
• Fast Compressed Self-Indexes with Deterministic Linear-Time Construction
• String attractors and infinite words
• Balancing run-length straight-line programs
• Substring complexities on run-length compressed strings
• Near-optimal search time in -optimal space, and vice versa
• String Attractors of Fixed Points of k-Bonacci-Like Morphisms
• Near-optimal search time in -optimal space
• Compressibility measures for two-dimensional data
• Computing all-vs-all MEMs in grammar-compressed text
• Iterated straight-line programs
• Space-efficient conversions from SLPs
• Sparse suffix and LCP array: simple, direct, small, and fast
• String attractors of some simple-parry automatic sequences
• Exploiting new properties of string net frequency for efficient computation
• The 2-attractor problem is NP-complete
• Substring complexity in sublinear space
• Computing NP-hard repetitiveness measures via MAX-SAT
• Online string attractors. And their relation to the Lempel-Ziv factorization
• Generalized straight-line programs
• Computing MEMs and relatives on repetitive text collections
• LZ78 substring compression in compressed space
• Generalization of repetitiveness measures for two-dimensional strings
• Optimal-time queries on BWT-runs compressed indexes
• Sparse suffix and LCP array: simple, direct, small, and fast
• Two-dimensional longest common extension queries in compact space
• Counting on general run-length grammars
• Grammar index by induced suffix sorting
• A compressed dynamic self-index for highly repetitive text collections

This page was built for publication: Optimal-Time Dictionary-Compressed Indexes

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