Rank and select revisited and extended
From MaRDI portal
Publication:2465064
DOI10.1016/j.tcs.2007.07.013zbMath1144.68023MaRDI QIDQ2465064
Publication date: 19 December 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2007.07.013
range searching; succinct data structures; compressed data structures; wavelet trees; position-restricted substring searching; gap encoding; substring rank and select
68P10: Searching and sorting
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68P05: Data structures
Related Items
Unnamed Item, Practical Wavelet Tree Construction, Efficient Data Structures for the Orthogonal Range Successor Problem, Unnamed Item, Unnamed Item, Generating spanning-tree sequences of a fan graph in lexicographic order and ranking/unranking algorithms, On representing the degree sequences of sublogarithmic-degree Wheeler graphs, Succinct data structure for path graphs, Compact binary relation representations with rich functionality, Space efficient data structures for dynamic orthogonal range counting, Colored range queries and document retrieval, On compressing and indexing repetitive sequences, Space-efficient data-analysis queries on grids, On compressing permutations and adaptive sorting, Bidirectional search in a string with wavelet trees and bidirectional matching statistics, Improved algorithms for the range next value problem and applications, Efficient fully-compressed sequence representations, Efficient dynamic range minimum query, Substring range reporting, Space-efficient construction of Lempel-Ziv compressed text indexes, Improved data structures for the orthogonal range successor problem, Succinct data structures for searchable partial sums with optimal worst-case performance, Improved parallel construction of wavelet trees and rank/select structures, Compact and succinct data structures for multidimensional orthogonal range searching, Dynamic extended suffix arrays, On compact representations of all-pairs-shortest-path-distance matrices, Faster entropy-bounded compressed suffix trees, Internal dictionary matching, Window queries for intersecting objects, maximal points and approximations using coresets, Amortized efficiency of generation, ranking and unranking left-child sequences in lexicographic order, Improved and extended locating functionality on compressed suffix arrays, Stronger Lempel-Ziv based compressed text indexing, Wavelet trees for all, Fully Functional Static and Dynamic Succinct Trees, Succinct and Implicit Data Structures for Computational Geometry, Array Range Queries, Amortized Efficiency of Ranking and Unranking Left-Child Sequences in Lexicographic Order, Time-Optimal Top-$k$ Document Retrieval, Self-indexing Based on LZ77, Counting Colours in Compressed Strings, On Wavelet Tree Construction, Substring Range Reporting, Self-indexed Text Compression Using Straight-Line Programs, Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Representing trees of higher degree
- A simple storage scheme for strings achieving entropy bounds
- Indexing text using the Ziv--Lempel trie
- Optimal lower bounds for rank and select indexes
- When indexing equals compression
- Compressed representations of sequences and full-text indexes
- Suffix Arrays: A New Method for On-Line String Searches
- An analysis of the Burrows—Wheeler transform
- Boosting textual compression in optimal linear time
- Indexing compressed text
- Squeezing succinct data structures into entropy bounds
- Universal codeword sets and representations of the integers
- New text indexing functionalities of the compressed suffix arrays
- 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
- Dynamic Entropy-Compressed Sequences and Full-Text Indexes
- Compressed Dictionaries: Space Measures, Data Sets, and Experiments
- String Processing and Information Retrieval
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
