A linear size index for approximate pattern matching

DOI10.1016/j.jda.2011.04.004zbMath1230.68223OpenAlexW2036463783WikidataQ58062906 ScholiaQ58062906MaRDI QIDQ655440

Siu-Lung Tam, Tak-Wah Lam, Wing-Kin Sung, Ho-Leung Chan, Swee-Seong Wong

Publication date: 4 January 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2011.04.004

zbMATH Keywords

space complexityapproximate pattern matchingfull text indexingindexing with errors

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computing methodologies for text processing; mathematical typography (68U15) Algorithms on strings (68W32)

Related Items

Approximate search of short patterns with high error rates using the \(01^\ast 0\) lossless seeds ⋮ Fast String Dictionary Lookup with One Error ⋮ Lossless Seeds for Searching Short Patterns with High Error Rates ⋮ Improved space-time tradeoffs for approximate full-text indexing with one edit error ⋮ Index structures for fast similarity search for binary vectors ⋮ String indexing for patterns with wildcards ⋮ Orthogonal Range Searching for Text Indexing

Cites Work

• Unnamed Item
• Unnamed Item
• Text indexing with errors
• Improved approximate string matching using compressed suffix data structures
• Compressed suffix trees with full functionality
• Suffix Arrays: A New Method for On-Line String Searches
• Dictionary matching and indexing with errors and don't cares
• A Space-Economical Suffix Tree Construction Algorithm
• Text Indexing and Dictionary Matching with One Error
• Combinatorial Pattern Matching
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching