A Faster Algorithm Computing String Edit Distances
Author(s)
Masek, William J.; Patterson, Michael S.
DownloadMIT-LCS-TM-105.pdf (4.036Mb)
Metadata
Show full item recordAbstract
The edit-distance between two character strings can be defined as the minimum cost of a sequence of editing operations which transforms one string into the other. The operations allowed are deleteing, inserting and replacing one symbol at a time, with possibly different costs for each of these operations. The problem of finding the logest common subsequence of two strings is a special case of the problem of computing edit-distances. We describe an algorithm for computing the edit-distance between two strings of length n and m, n>=m, which requires 0(nm/min(log n, m)) steps whenever the costs of edit-operations are integral multiples of a single positive real number and the alphabet for the strings is finite. These conditions are necessary for the algorithm to achieve the time bound.
Date issued
1978-05Series/Report no.
MIT-LCS-TM-105