A sublinear algorithm for approximate keyword searching
From MaRDI portal
Publication:1336965
DOI10.1007/BF01185432zbMath0941.68560OpenAlexW2165156013MaRDI QIDQ1336965
Publication date: 26 February 1996
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01185432
Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Protein sequences, DNA sequences (92D20) Information storage and retrieval of data (68P20)
Related Items
A metric index for approximate string matching, New and faster filters for multiple approximate string matching, Multiple filtration and approximate pattern matching, A subquadratic algorithm for approximate limited expression matching, Approximate string matching with compressed indexes, Multiple approximate string matching, Fast Approximate Search in Large Dictionaries, Text indexing with errors, Efficient generation of super condensed neighborhoods, What’s Behind Blast, A new method for approximate indexing and dictionary lookup with one error, Indexing text with approximate \(q\)-grams
Cites Work
- An \(O(ND)\) difference algorithm and its variations
- A subquadratic algorithm for approximate limited expression matching
- A fast string searching algorithm
- An Improved Algorithm For Approximate String Matching
- Finding approximate patterns in strings
- Algorithms for approximate string matching
- The theory and computation of evolutionary distances: Pattern recognition
- Fast Pattern Matching in Strings