Optimal-Time Dictionary-Compressed Indexes

DOI10.1145/3426473OpenAlexW3116542221MaRDI QIDQ5028345

Mikko Berggren Ettienne, Anders Roy Christiansen, Nicola Prezza, Tomasz Kociumaka, 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

attractorsgrammar compressionlocally consistent parsingrepetitive string collectionscompressed text indexes

Mathematics Subject Classification ID

Computer science (68-XX)

Related Items (14)

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 ⋮ Grammar-compressed indexes with logarithmic search time ⋮ 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 of Fixed Points of k-Bonacci-Like Morphisms ⋮ Near-optimal search time in \(\delta \)-optimal space ⋮ Sensitivity of string compressors and repetitiveness measures ⋮ A compressed dynamic self-index for highly repetitive text collections

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