Myers, Eugene W.:
*An O(ND) difference algorithm and
its variations*;
Algorithmica 1:2, p.251-266;
1986

*Download: *Volltext

*Deskriptoren: *CVSM
*Abstract: *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) and is
consequently fast in typical applications. The algorithm
is shown to have O(N + D**2) expected-time performance
under a basic stochastic model. A refinement of the
algorithm requires only O(N) space, and the use of suffix
trees leads to an O(NlgN + D**2) time
variation.