Compressed text indexing with wildcards
From MaRDI portal
Publication:2434928
DOI10.1016/j.jda.2012.12.003zbMath1280.68305OpenAlexW2049569569MaRDI QIDQ2434928
Wing-Kai Hon, Jeffrey Scott Vitter, Tsung-Han Ku, Rahul Shah, Sharma V. Thankachan
Publication date: 3 February 2014
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2012.12.003
Database theory (68P15) Combinatorics in computer science (68R05) Computing methodologies for text processing; mathematical typography (68U15) Algorithms on strings (68W32)
Related Items (5)
Less space: indexing for queries with wildcards ⋮ On position restricted substring searching in succinct space ⋮ Compressed indexes for text with wildcards ⋮ On the average-case complexity of pattern matching with wildcards ⋮ Geometric BWT: compressed text indexing via sparse suffixes and range searching
Cites Work
- A simple storage scheme for strings achieving entropy bounds
- Orthogonal range searching in linear and almost-linear space
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Faster compressed dictionary matching
- Compressed representations of sequences and full-text indexes
- Succincter Text Indexing with Wildcards
- Suffix Arrays: A New Method for On-Line String Searches
- Indexing compressed text
- Succinct Dictionary Matching with No Slowdown
- Deterministic sorting in O ( n log log n ) time and linear space
- Dictionary matching and indexing with errors and don't cares
- A Space-Economical Suffix Tree Construction Algorithm
- Text Indexing and Dictionary Matching with One Error
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- Space Efficient Indexes for String Matching with Don’t Cares
- Orthogonal range searching on the RAM, revisited
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
This page was built for publication: Compressed text indexing with wildcards
