AnO(ND) difference algorithm and its variations
EW Myers - Algorithmica, 1986 - Springer
Algorithmica, 1986•Springer
The problems of finding a longest common subsequence of two sequences A and B and a
shortest edit script for transforming A into B have long been known to be dual problems. In
this paper, they are shown to be equivalent to finding a shortest/longest path in an edit
graph. Using this perspective, a simple O (ND) time and space algorithm is developed
where N is the sum of the lengths of A and B and D is the size of the minimum edit script for
A and B. The algorithm performs well when differences are small (sequences are similar) …
shortest edit script for transforming A into B have long been known to be dual problems. In
this paper, they are shown to be equivalent to finding a shortest/longest path in an edit
graph. Using this perspective, a simple O (ND) time and space algorithm is developed
where N is the sum of the lengths of A and B and D is the size of the minimum edit script for
A and B. The algorithm performs well when differences are small (sequences are similar) …
Abstract
The problems of finding a longest common subsequence of two sequencesA andB and a shortest edit script for transformingA intoB have long been known to be dual problems. In this paper, they are shown to be equivalent to finding a shortest/longest path in an edit graph. Using this perspective, a simpleO(ND) time and space algorithm is developed whereN is the sum of the lengths ofA andB andD is the size of the minimum edit script forA andB. The algorithm performs well when differences are small (sequences are similar) and is consequently fast in typical applications. The algorithm is shown to haveO(N+D 2) expected-time performance under a basic stochastic model. A refinement of the algorithm requires onlyO(N) space, and the use of suffix trees leads to anO(N logN+D 2) time variation.
Springer