Approximate String Matching
Patrick A. V. Hall, Geoff R. Dowling · ACM Computing Surveys · 1980
Approximate matching of strings is reviewed with the aim of surveying techniques suitable for finding an item in a database when there may be a spelling mistake or other error in the keyword.The methods found are classified as either equivalence or similarity problems.Equivalence problems are seen to be readily solved using canonical forms.For sinuiarity problems difference measures are surveyed, with a full description of the wellestablmhed dynamic programming method relating this to the approach using probabilities and likelihoods.Searches for approximate matches in large sets using a difference function are seen to be an open problem still, though several promising ideas have been suggested.Approximate matching (error correction) during parsing is briefly reviewed.
Cited by 584 works. doi:10.1145/356827.356830 Open-access PDF
Authors
References
- Error-Correcting Codes.
- Formal Languages and Their Relation to Automata
- The String-to-String Correction Problem
- Fast Pattern Matching in Strings
- Spelling correction in systems programs
- Sorting and Searching
- Binary codes capable of correcting deletions, insertions and reversals
- Efficient string matching
- A fast string searching algorithm
- Efficiency of a Good But Not Linear Set Union Algorithm