Improved approximate string matching using compressed suffix data structures

DOI10.1007/S00453-007-9104-8zbMath1203.68040OpenAlexW2615813815MaRDI QIDQ930602

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

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

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

Related Items (7)

Fast String Dictionary Lookup with One Error ⋮ Unnamed Item ⋮ A linear size index for approximate pattern matching ⋮ Improved space-time tradeoffs for approximate full-text indexing with one edit error ⋮ Cache-oblivious index for approximate string matching ⋮ Compressed indexes for approximate string matching ⋮ Streaming dictionary matching with mismatches

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Time-space trade-offs for compressed suffix arrays.
• Compressed suffix trees with full functionality
• Space Efficient Suffix Trees
• Succinct Representation of Balanced Parentheses and Static Trees
• Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
• Dictionary matching and indexing with errors and don't cares
• The theory and computation of evolutionary distances: Pattern recognition
• Fast parallel and serial approximate string matching
• Text Indexing and Dictionary Matching with One Error
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Combinatorial Pattern Matching

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