Wavelet trees for all
From MaRDI portal
Publication:2442812
DOI10.1016/j.jda.2013.07.004zbMath1284.68217OpenAlexW2086536051MaRDI QIDQ2442812
Publication date: 1 April 2014
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2013.07.004
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)
Related Items (23)
Compressed matching for feature vectors ⋮ Fast construction of wavelet trees ⋮ Document listing on repetitive collections with guaranteed performance ⋮ Wavelet analysis on symbolic sequences and two-fold de Bruijn sequences ⋮ Parallel lightweight wavelet tree, suffix array and FM-index construction ⋮ Range selection and predecessor queries in data aware space and time ⋮ Grammar compressed sequences with rank/select support ⋮ Grammar-compressed indexes with logarithmic search time ⋮ Practical space-efficient index for structural pattern matching ⋮ Succinct encodings for families of interval graphs ⋮ Compact representations of spatial hierarchical structures with support for topological queries ⋮ Practical Wavelet Tree Construction ⋮ Using compressed suffix-arrays for a compact representation of temporal-graphs ⋮ Unnamed Item ⋮ A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs ⋮ Space-efficient construction of compressed suffix trees ⋮ Simpler FM-index for parameterized string matching ⋮ A Self-index on Block Trees ⋮ Efficient and compact representations of some non-canonical prefix-free codes ⋮ Space-efficient computation of the LCP array from the Burrows-Wheeler transform ⋮ Space-efficient fully dynamic DFS in undirected graphs ⋮ Computing the Burrows-Wheeler transform in place and in small space ⋮ Structural Pattern Matching - Succinctly.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Compact binary relation representations with rich functionality
- Space-efficient data-analysis queries on grids
- On compressing permutations and adaptive sorting
- New algorithms on wavelet trees and applications to information retrieval
- Indexing text using the Ziv--Lempel trie
- The myriad virtues of wavelet trees
- Rank and select revisited and extended
- Optimal lower bounds for rank and select indexes
- Fully Functional Static and Dynamic Succinct Trees
- New Lower and Upper Bounds for Representing Sequences
- Compressed representations of sequences and full-text indexes
- Compressed indexes for dynamic text collections
- Self-indexing Based on LZ77
- Counting Colours in Compressed Strings
- On Wavelet Tree Construction
- Alphabet Partitioning for Compressed Rank/Select and Applications
- Entropy-Bounded Representation of Point Grids
- Alphabet-Independent Compressed Text Indexing
- Suffix Arrays: A New Method for On-Line String Searches
- Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
- Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
- An analysis of the Burrows—Wheeler transform
- Self-Indexed Grammar-Based Compression
- Fast and Compact Prefix Codes
- Space-Efficient Algorithms for Document Retrieval
- Compressed Text Indexes with Fast Locate
- Position-Restricted Substring Searching
- On the Size of Succinct Indices
- Boosting textual compression in optimal linear time
- Indexing compressed text
- Optimal Succinctness for Range Minimum Queries
- Compact Rich-Functional Binary Relation Representations
- Extended Compact Web Graph Representations
- Bidirectional Search in a String with Wavelet Trees
- Rank/select operations on large alphabets
- Top-k Ranked Document Search in General Text Databases
- Optimal Lower Bounds for Rank and Select Indexes
- A Space-Economical Suffix Tree Construction Algorithm
- A Functional Approach to Data Structures and Its Use in Multidimensional Searching
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- Optimal Dynamic Sequence Representations
- Practical Entropy-Compressed Rank/Select Dictionary
- Efficient Data Structures for the Orthogonal Range Successor Problem
- COMPRESSED REPRESENTATIONS OF PERMUTATIONS, AND APPLICATIONS
- String Processing and Information Retrieval
- Orthogonal range searching on the RAM, revisited
- An experimental investigation of set intersection algorithms for text searching
- A Primer on Wavelets and Their Scientific Applications
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections
- A Method for the Construction of Minimum-Redundancy Codes
- Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
This page was built for publication: Wavelet trees for all
