Dynamic rank/select structures with applications to run-length encoded texts

DOI10.1016/j.tcs.2009.07.021zbMath1181.68121OpenAlexW2112179489MaRDI QIDQ732034

Sunho Lee, Kun Soo Park

Publication date: 9 October 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.07.021

zbMATH Keywords

run-length encodingsuccinct data structuresdynamic rank/select structuresfull-text index

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Algorithms on strings (68W32)

Related Items

Fast construction of wavelet trees, Compressed Data Structures for Dynamic Sequences, An Opportunistic Text Indexing Structure Based on Run Length Encoding

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple storage scheme for strings achieving entropy bounds
• Compressed representations of sequences and full-text indexes
• An analysis of the Burrows—Wheeler transform
• On the Size of Succinct Indices
• Rank/select operations on large alphabets
• Squeezing succinct data structures into entropy bounds
• New text indexing functionalities of the compressed suffix arrays
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Dynamic entropy-compressed sequences and full-text indexes
• Algorithms and Computation
• Dynamic Entropy-Compressed Sequences and Full-Text Indexes
• Combinatorial Pattern Matching
• A Framework for Dynamizing Succinct Data Structures
• Improved Dynamic Rank-Select Entropy-Bound Structures
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Combinatorial Pattern Matching