Improved approximate string matching using compressed suffix data structures

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

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

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

Mathematics Subject Classification ID

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

Cites Work

• 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)
• Title not available (Why is that?)
• 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)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Time-space trade-offs for compressed suffix arrays.
• Title not available (Why is that?)
• Combinatorial Pattern Matching
• Title not available (Why is that?)

Cited In (15)

• Combinatorial Pattern Matching
• Approximate string processing
• 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
• Approximate string matching with reduced alphabet
• Approximate string matching using compressed suffix arrays
• Compressed indexes for approximate string matching
• Data structures and algorithms 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
• Title not available (Why is that?)
• Algorithms and Computation

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)