Rank and select revisited and extended

DOI10.1016/j.tcs.2007.07.013zbMath1144.68023OpenAlexW2130080588MaRDI QIDQ2465064

Gonzalo Navarro, Veli Mäkinen

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

zbMATH Keywords

range searchingsuccinct data structurescompressed data structureswavelet treesposition-restricted substring searchinggap encodingsubstring rank and select

Mathematics Subject Classification ID

Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)

Related Items (44)

Self-indexed Text Compression Using Straight-Line Programs ⋮ Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing ⋮ Efficient Data Structures for the Orthogonal Range Successor Problem ⋮ 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 ⋮ Improved data structures for the orthogonal range successor problem ⋮ Practical Wavelet Tree Construction ⋮ 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 ⋮ Amortized Efficiency of Ranking and Unranking Left-Child Sequences in Lexicographic Order ⋮ Bidirectional search in a string with wavelet trees and bidirectional matching statistics ⋮ Unnamed Item ⋮ Stronger Lempel-Ziv based compressed text indexing ⋮ Succinct data structure for path graphs ⋮ Time-Optimal Top-$k$ Document Retrieval ⋮ Improved algorithms for the range next value problem and applications ⋮ Wavelet trees for all ⋮ Efficient fully-compressed sequence representations ⋮ Window queries for intersecting objects, maximal points and approximations using coresets ⋮ Efficient dynamic range minimum query ⋮ Self-indexing Based on LZ77 ⋮ Counting Colours in Compressed Strings ⋮ On Wavelet Tree Construction ⋮ Substring Range Reporting ⋮ Substring range reporting ⋮ Dynamic extended suffix arrays ⋮ Space-efficient construction of Lempel-Ziv compressed text indexes ⋮ Amortized efficiency of generation, ranking and unranking left-child sequences in lexicographic order ⋮ On compact representations of all-pairs-shortest-path-distance matrices ⋮ Unnamed Item ⋮ Succinct data structures for searchable partial sums with optimal worst-case performance ⋮ Fully Functional Static and Dynamic Succinct Trees ⋮ Internal dictionary matching ⋮ Faster entropy-bounded compressed suffix trees ⋮ Improved parallel construction of wavelet trees and rank/select structures ⋮ Compact and succinct data structures for multidimensional orthogonal range searching ⋮ Succinct and Implicit Data Structures for Computational Geometry ⋮ Array Range Queries ⋮ Unnamed Item ⋮ Improved and extended locating functionality on compressed suffix arrays

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

This page was built for publication: Rank and select revisited and extended