Improved approximate string matching using compressed suffix data structures

DOI10.1007/S00453-007-9104-8MaRDI QIDQ930602zbMATH OpenOpenAlexFDO

Authors Tak-Wah Lam, Wing-Kin Sung, Swee-Seong Wong

Publication date 1 July 2008

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-007-9104-8

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Data structures (68P05) Searching and sorting (68P10)

Recommendations

• Algorithms and Computation
• Combinatorial Pattern Matching
• Approximate string matching using compressed suffix arrays
• Compressed Indexes for Approximate String Matching
• Compressed indexes for approximate string matching

Cites work

• scientific article; zbMATH DE number 1615292 (Why is no real title available?)
• scientific article; zbMATH DE number 1670652 (Why is no real title available?)
• scientific article; zbMATH DE number 2185640 (Why is no real title available?)
• scientific article; zbMATH DE number 176144 (Why is no real title available?)
• scientific article; zbMATH DE number 1445379 (Why is no real title available?)
• Combinatorial Pattern Matching
• Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
• Compressed suffix trees with full functionality
• Dictionary matching and indexing with errors and don't cares
• Fast parallel and serial approximate string matching
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Space efficient suffix trees
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Succinct representation of balanced parentheses and static trees
• Text Indexing and Dictionary Matching with One Error
• The theory and computation of evolutionary distances: Pattern recognition
• Time-space trade-offs for compressed suffix arrays.

Cited in

(15)

• A linear size index for approximate pattern matching
• Streaming dictionary matching with mismatches
• Cache-oblivious index for approximate string matching
• Algorithms and Computation
• Fast string dictionary lookup with one error
• Approximate string matching with reduced alphabet
• Combinatorial Pattern Matching
• Compressed indexes for approximate string matching
• Approximate string processing
• Approximate string matching with compressed indexes
• Data structures and algorithms for approximate string matching
• scientific article; zbMATH DE number 1790365 (Why is no real title available?)
• Fast entropy-bounded string dictionary look-up with mismatches
• Improved space-time tradeoffs for approximate full-text indexing with one edit error
• Approximate string matching using compressed suffix arrays

This page was built for publication: Improved approximate string matching using compressed suffix data structures

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