Premium
An improved adaptive string searching algorithm
Author(s) -
Liu Z.,
Du X.,
Ishi N.
Publication year - 1998
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(199802)28:2<191::aid-spe149>3.0.co;2-2
Subject(s) - character (mathematics) , algorithm , alphabet , computer science , string (physics) , independence (probability theory) , adaptive algorithm , mathematics , statistics , linguistics , philosophy , geometry , mathematical physics
Sunday's OM algorithm can reduce the number of character comparisons by making use of information of character distribution in an alphabet. Smith's adaptive algorithm uses dynamic statistics to reduce comparisons and its performance is close to that of the OM algorithm in the number of character comparisons. Smith's algorithm has the advantage of language independence. Its drawback is that it runs slowly because of maintaining an ordering list. This paper presents an improved adaptive method which dispenses with the ordering list. This method treats the pattern as a circle, and first compares the mismatched character in the last checking operation. This methods is slightly worse than Smith's method in the number of character comparisons, but it much better in the running time. © 1998 John Wiley & Sons, Ltd.