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

DOI10.1016/J.TCS.2009.07.021zbMATH Open1181.68121OpenAlexW2112179489MaRDI QIDQ732034FDOQ732034

Authors: Sunho Lee, Kunsoo 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

Recommendations

• Dynamic Rank-Select Structures with Applications to Run-Length Encoded Texts
• Improved Dynamic Rank-Select Entropy-Bound Structures
• Rank/select on dynamic compressed sequences and applications
• Rank and select revisited and extended

zbMATH Keywords

succinct data structuresrun-length encodingdynamic rank/select structuresfull-text index

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Dynamic Rank-Select Structures with Applications to Run-Length Encoded Texts
• Compressed Data Structures for Dynamic Sequences
• Fast construction of wavelet trees
• Improved Dynamic Rank-Select Entropy-Bound Structures
• An Opportunistic Text Indexing Structure Based on Run Length Encoding
• Rank/select on dynamic compressed sequences and applications
• Rank and select revisited and extended
• A practical alphabet-partitioning rank/select data structure

This page was built for publication: Dynamic rank/select structures with applications to run-length encoded texts

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