| Abstract: | 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. |
