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

DOI10.1016/J.TCS.2009.07.021MaRDI QIDQ732034zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)