An Opportunistic Text Indexing Structure Based on Run Length Encoding

DOI10.1007/978-3-319-18173-8_29MaRDI QIDQ2947038zbMATH OpenOpenAlexFDO

Authors Yuya Tamakoshi, Keisuke Goto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Publication date 21 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-18173-8_29

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
• Dynamic Rank-Select Structures with Applications to Run-Length Encoded Texts
• Fast and simple jumbled indexing for binary run-length encoded strings
• scientific article; zbMATH DE number 6850405
• Optimal construction of compressed indexes for highly repetitive texts
• scientific article; zbMATH DE number 7651115
• scientific article; zbMATH DE number 1003303
• Indexing text using the Ziv--Lempel trie
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• scientific article; zbMATH DE number 2079421

Cites work

• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• scientific article; zbMATH DE number 2230164 (Why is no real title available?)
• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• A universal algorithm for sequential data compression
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Dynamic rank/select structures with applications to run-length encoded texts
• Faster compact on-line Lempel-Ziv factorization
• Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism
• Optimal lower bounds for rank and select indexes
• Parameterized searching with mismatches for run-length encoded strings
• Space efficient linear time construction of suffix arrays
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Suffix Arrays: A New Method for On-Line String Searches
• Two Efficient Algorithms for Linear Time Suffix Array Construction
• Wavelet trees for all

Cited in

(2)

• Dynamic Rank-Select Structures with Applications to Run-Length Encoded Texts
• Reverse-safe text indexing

This page was built for publication: An Opportunistic Text Indexing Structure Based on Run Length Encoding

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