Premium
A Comparison of Approximate String Matching Algorithms
Author(s) -
JOKINEN PETTERI,
TARHIO JORMA,
UKKONEN ESKO
Publication year - 1996
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/(sici)1097-024x(199612)26:12<1439::aid-spe71>3.0.co;2-1
Subject(s) - string searching algorithm , approximate string matching , commentz walter algorithm , string metric , string (physics) , algorithm , boyer–moore string search algorithm , pattern matching , matching (statistics) , dynamic programming , automaton , suffix , computer science , combinatorics , mathematics , theoretical computer science , artificial intelligence , linguistics , statistics , philosophy , mathematical physics
Experimental comparisons of the running time of approximate string matching algorithms for the k differences problem are presented. Given a pattern string, a text string, and an integer k , the task is to find all approximate occurrences of the pattern in the text with at most k differences (insertions, deletions, changes). We consider seven algorithms based on different approaches including dynamic programming, Boyer–Moore string matching, suffix automata, and the distribution of characters. It turns out that none of the algorithms is the best for all values of the problem parameters, and the speed differences between the methods can be considerable.