Faster entropy-bounded compressed suffix trees
From MaRDI portal
Publication:1038474
DOI10.1016/j.tcs.2009.09.012zbMath1187.68171WikidataQ56768697 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
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68P05: Data structures
Related Items
Faster Compressed Suffix Trees for Repetitive Collections, Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies, Practical Performance of Space Efficient Data Structures for Longest Common Extensions., Balancing run-length straight-line programs, Compressed indexes for text with wildcards, On compressing and indexing repetitive sequences, Multi-pattern matching with bidirectional indexes, Cross-document pattern matching, Combined data structure for previous- and next-smaller-values, Wee LCP, Encoding nearest larger values, Practical compressed suffix trees, LRM-trees: compressed indices, adaptive sorting, and compressed permutations, Improved and extended locating functionality on compressed suffix arrays, Succinct 2D dictionary matching, Improved range minimum queries, Speeding up the detection of tandem repeats over the edit distance, Space efficient data structures for nearest larger neighbor, Faster repetition-aware compressed suffix trees based on block trees, Locally Compressed Suffix Arrays, Encoding Nearest Larger Values, Space Efficient Data Structures for Nearest Larger Neighbor, The longest common substring problem, Succincter Text Indexing with Wildcards, LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations
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