AN EXTENSION OF UKKONENS ENHANCED DYNAMIC-PROGRAMMING ASM ALGORITHM

We describe an improvement on Ukkonen's Enhanced Dynamic Programming ( EHD) approximate string-matching algorithm for unit-penalty four-edit comparisons. The new algorithm has an asymptotic complexity similar to that of Ukkonen's but is significantly faster due to a decrease in th e number of array cell calculations. A 42% speedup was achieved in an application involving name comparisons, Even greater improvements are possible when comparing longer and more dissimilar strings. Although t he speed of the algorithm under consideration is comparable to other f ast ASM algorithms, it has greater effectiveness in text-processing ap plications because it supports all four basic Damerau-type editing ope rations.