An extension of Ukkonen's enhanced dynamic programming ASM algorithm
- 11 January 1996
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Information Systems
- Vol. 14 (1) , 94-106
- https://doi.org/10.1145/214174.214183
Abstract
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 the 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 the speed of the algorithm under consideration is comparable to other fast ASM algorithms, it has greater effectiveness in text-processing applications because it supports all four basic Damerau-type editing operations.Keywords
This publication has 8 references indexed in Scilit:
- Fast text searchingCommunications of the ACM, 1992
- An O(NP) sequence comparison algorithmInformation Processing Letters, 1990
- Data structures and algorithms for approximate string matchingJournal of Complexity, 1988
- A logical framework for the correction of spelling errors in electronic documentsInformation Processing & Management, 1987
- On the Theory and Computation of Evolutionary DistancesSIAM Journal on Applied Mathematics, 1974
- The String-to-String Correction ProblemJournal of the ACM, 1974
- An inductive approach to language translationCommunications of the ACM, 1964
- A technique for computer detection and correction of spelling errorsCommunications of the ACM, 1964