Compressed text indexing with wildcards

DOI10.1016/J.JDA.2012.12.003MaRDI QIDQ2434928zbMATH OpenOpenAlexFDO

Authors Wing-Kai Hon, Tsung-Han Ku, Rahul Shah, Sharma V. Thankachan, Jeffrey Scott Vitter

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

zbMATH Keywords

approximate pattern matchingcompressed text indexingwildcards

Mathematics Subject Classification ID

Database theory (68P15) Combinatorics in computer science (68R05) Computing methodologies for text processing; mathematical typography (68U15) Algorithms on strings (68W32)

Recommendations

• Compressed indexes for text with wildcards
• Succincter text indexing with wildcards
• Universal compressed text indexing
• Compressed indexes for dynamic text collections
• Compressed text indexes, from theory to practice
• Combinatorial Pattern Matching
• Indexing compressed text

Cites work

• A simple storage scheme for strings achieving entropy bounds
• A Space-Economical Suffix Tree Construction Algorithm
• Compressed representations of sequences and full-text indexes
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Deterministic sorting in O ( n log log n ) time and linear space
• Dictionary matching and indexing with errors and don't cares
• Faster compressed dictionary matching
• Indexing compressed text
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Orthogonal range searching in linear and almost-linear space
• Orthogonal range searching on the RAM, revisited
• Space Efficient Indexes for String Matching with Don’t Cares
• Succinct Dictionary Matching with No Slowdown
• Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets
• Succincter text indexing with wildcards
• Suffix Arrays: A New Method for On-Line String Searches
• Text Indexing and Dictionary Matching with One Error

Cited in

(7)

• Geometric BWT: compressed text indexing via sparse suffixes and range searching
• On position restricted substring searching in succinct space
• On the average-case complexity of pattern matching with wildcards
• Less space: indexing for queries with wildcards
• Succincter text indexing with wildcards
• Compressed Text Indexes with Fast Locate
• Compressed indexes for text with wildcards

This page was built for publication: Compressed text indexing with wildcards

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2434928)