Faster entropy-bounded compressed suffix trees
From MaRDI portal
Publication:1038474
DOI10.1016/j.tcs.2009.09.012zbMath1187.68171OpenAlexW2154803978WikidataQ56768697 ScholiaQ56768697MaRDI QIDQ1038474
Johannes Fischer, Veli Mäkinen, Gonzalo Navarro
Publication date: 18 November 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.09.012
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)
Related Items (25)
Space efficient data structures for nearest larger neighbor ⋮ Succinct 2D dictionary matching ⋮ Improved range minimum queries ⋮ Encoding Nearest Larger Values ⋮ Space Efficient Data Structures for Nearest Larger Neighbor ⋮ Compressed indexes for text with wildcards ⋮ On compressing and indexing repetitive sequences ⋮ Faster repetition-aware compressed suffix trees based on block trees ⋮ Multi-pattern matching with bidirectional indexes ⋮ Cross-document pattern matching ⋮ Balancing run-length straight-line programs ⋮ Encoding nearest larger values ⋮ The longest common substring problem ⋮ Speeding up the detection of tandem repeats over the edit distance ⋮ Practical Performance of Space Efficient Data Structures for Longest Common Extensions. ⋮ Practical compressed suffix trees ⋮ Succincter Text Indexing with Wildcards ⋮ LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations ⋮ LRM-trees: compressed indices, adaptive sorting, and compressed permutations ⋮ Combined data structure for previous- and next-smaller-values ⋮ Wee LCP ⋮ Locally Compressed Suffix Arrays ⋮ Improved and extended locating functionality on compressed suffix arrays ⋮ Faster Compressed Suffix Trees for Repetitive Collections ⋮ Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Nearest common ancestors: a survey and a new algorithm for a distributed environment
- A simple optimal representation for balanced parentheses
- Replacing suffix trees with enhanced suffix arrays
- Succinct data structures for flexible text retrieval systems
- Suffix trays and suffix trists: structures for faster text indexing
- Compressed suffix trees with full functionality
- Rank and select revisited and extended
- Space Efficient Suffix Trees
- Compressed representations of sequences and full-text indexes
- Compressed indexes for dynamic text collections
- An analysis of the Burrows—Wheeler transform
- Compressed Text Indexes with Fast Locate
- An(other) Entropy-Bounded Compressed Suffix Tree
- Finding Patterns in Given Intervals
- Linear-Time Construction of Suffix Arrays
- Space Efficient Linear Time Construction of Suffix Arrays
- A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
- Optimal Lower Bounds for Rank and Select Indexes
- Recursive Star-Tree Parallel Data Structure
- Algorithms on Strings, Trees and Sequences
- A Generalized Suffix Tree and Its (Un)Expected Asymptotic Behaviors
- New text indexing functionalities of the compressed suffix arrays
- Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
- Engineering the LOUDS Succinct Tree Representation
- Compressed text indexes
- Fully-Compressed Suffix Trees
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- Lowest common ancestors in trees and directed acyclic graphs
This page was built for publication: Faster entropy-bounded compressed suffix trees
