Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings
From MaRDI portal
Publication:4928577
DOI10.1007/978-3-642-38905-4_24zbMath1381.68073arXiv1203.1080OpenAlexW1800468673MaRDI QIDQ4928577
Publication date: 14 June 2013
Published in: Combinatorial Pattern Matching (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1203.1080
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42) Data structures (68P05)
Related Items (14)
Block graphs in practice ⋮ Access, Rank, and Select in Grammar-compressed Strings ⋮ Document listing on repetitive collections with guaranteed performance ⋮ Grammar compressed sequences with rank/select support ⋮ Grammar-compressed indexes with logarithmic search time ⋮ Balancing run-length straight-line programs ⋮ Random access in persistent strings and segment selection ⋮ Unnamed Item ⋮ Block trees ⋮ Optimal rank and select queries on dictionary-compressed text ⋮ Finger search in grammar-compressed strings ⋮ Random Access to High-Order Entropy Compressed Text ⋮ Random Access to Grammar-Compressed Strings and Trees ⋮ Approximate pattern matching in LZ77-compressed texts
This page was built for publication: Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings
