Improved approximate string matching using compressed suffix data structures

DOI10.1007/S00453-007-9104-8zbMATH Open1203.68040OpenAlexW2615813815MaRDI QIDQ930602FDOQ930602

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

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

Cites Work

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

Cited In (8)

• Streaming dictionary matching with mismatches
• 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
• Approximate string matching with compressed indexes
• Title not available (Why is that?)
• A linear size index for approximate pattern matching
• Fast String Dictionary Lookup with One Error

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)