A linear size index for approximate pattern matching

DOI10.1016/J.JDA.2011.04.004MaRDI QIDQ655440zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ho-Leung Chan, Tak-Wah Lam, Wing-Kin Sung, Siu-Lung Tam, 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) Algorithms on strings (68W32) Computing methodologies for text processing; mathematical typography (68U15)

Recommendations

• A Linear Size Index for Approximate Pattern Matching
• Compressed indexes for approximate string matching
• Compressed Indexes for Approximate String Matching
• Combinatorial Pattern Matching
• Text indexing with errors

Cites work

• scientific article; zbMATH DE number 1670652 (Why is no real title available?)
• scientific article; zbMATH DE number 2086228 (Why is no real title available?)
• A Space-Economical Suffix Tree Construction Algorithm
• Combinatorial Pattern Matching
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Compressed suffix trees with full functionality
• Dictionary matching and indexing with errors and don't cares
• Improved approximate string matching using compressed suffix data structures
• Suffix Arrays: A New Method for On-Line String Searches
• Text Indexing and Dictionary Matching with One Error
• Text indexing with errors

Cited in

(13)

• scientific article; zbMATH DE number 2185612 (Why is no real title available?)
• Combinatorial Pattern Matching
• Compressed Indexes for Approximate String Matching
• Cache-oblivious index for approximate string matching
• Fast string dictionary lookup with one error
• Orthogonal range searching for text indexing
• Index structures for fast similarity search for binary vectors
• A Linear Size Index for Approximate Pattern Matching
• Compressed indexes for approximate string matching
• Lossless seeds for searching short patterns with high error rates
• Improved space-time tradeoffs for approximate full-text indexing with one edit error
• Text indexing with errors
• Approximate search of short patterns with high error rates using the \(01^\ast 0\) lossless seeds

This page was built for publication: A linear size index for approximate pattern matching

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