An extension of Ukkonen's 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 the number o...

Full description

Bibliographic Details

Published in:	ACM transactions on information systems. 14, 1 (1996).
Main Author:	Berghel, Hal
Other Authors:	Roach, David
Format:	Article
Language:	English
Subjects:	Approximate string matching. Dynamic programming. Enhanced dynamic programming. Similarity relations.