diff options
Diffstat (limited to 'differ.txi')
| -rw-r--r-- | differ.txi | 60 |
1 files changed, 36 insertions, 24 deletions
@@ -6,14 +6,14 @@ S. Wu, E. Myers, U. Manber, and W. Miller, "An O(NP) Sequence Comparison Algorithm," Information Processing Letters 35, 6 (1990), 317-323. - @url{http://www.cs.arizona.edu/people/gene/vita.html} + @url{http://www.cs.arizona.edu/people/gene/PAPERS/np_diff.ps} @end example @end ifinfo @ifset html S. Wu, <A HREF="http://www.cs.arizona.edu/people/gene/vita.html"> E. Myers,</A> U. Manber, and W. Miller, <A HREF="http://www.cs.arizona.edu/people/gene/PAPERS/np_diff.ps"> -"An O(NP) Sequence Comparison Algorithm,"</A> +"An O(NP) Sequence Comparison Algorithm"</A>, Information Processing Letters 35, 6 (1990), 317-323. @end ifset @@ -22,12 +22,24 @@ The values returned by @code{diff:edit-length} can be used to gauge the degree of match between two sequences. @noindent -Surprisingly, "An O(NP) Sequence Comparison Algorithm" does not -derive the edit sequence; only the sequence length. Developing this -linear-space sub-quadratic-time algorithm for computing the edit -sequence required hundreds of hours of work. I have submitted a -paper describing the algorithm to the Journal of Computational -Biology. +@code{diff:edits} and @code{diff:longest-common-subsequence} combine +the algorithm with the divide-and-conquer method outlined in: + +@ifinfo +@example +E. Myers and W. Miller, + "Optimal alignments in linear space", + Computer Application in the Biosciences (CABIOS), 4(1):11-17, 1988. + @url{http://www.cs.arizona.edu/people/gene/PAPERS/linear.ps} +@end example +@end ifinfo +@ifset html +<A HREF="http://www.cs.arizona.edu/people/gene/vita.html"> +E. Myers,</A> and W. Miller, +<A HREF="http://www.cs.arizona.edu/people/gene/PAPERS/linear.ps"> +"Optimal alignments in linear space"</A>, +Computer Application in the Biosciences (CABIOS), 4(1):11-17, 1988. +@end ifset @noindent If the items being sequenced are text lines, then the computed @@ -38,12 +50,11 @@ lesser known @dfn{spiff} program. @cindex spiff -@defun diff:longest-common-subsequence array1 array2 =? p-lim +@defun diff:longest-common-subsequence array1 array2 p-lim -@defunx diff:longest-common-subsequence array1 array2 =? -@var{array1} and @var{array2} are one-dimensional arrays. The procedure @var{=?} is used -to compare sequence tokens for equality. +@defunx diff:longest-common-subsequence array1 array2 +@var{array1} and @var{array2} are one-dimensional arrays. The non-negative integer @var{p-lim}, if provided, is maximum number of deletions of the shorter sequence to allow. @code{diff:longest-common-subsequence} will return @code{#f} @@ -54,12 +65,12 @@ len1 len2) (diff:edit-length @var{array1} @var{array2})) 2)} holding the longest common to both @var{array}s. @end defun -@defun diff:edits array1 array2 =? p-lim + +@defun diff:edits array1 array2 p-lim -@defunx diff:edits array1 array2 =? -@var{array1} and @var{array2} are one-dimensional arrays. The procedure @var{=?} is used -to compare sequence tokens for equality. +@defunx diff:edits array1 array2 +@var{array1} and @var{array2} are one-dimensional arrays. The non-negative integer @var{p-lim}, if provided, is maximum number of deletions of the shorter sequence to allow. @code{diff:edits} will return @code{#f} @@ -77,12 +88,12 @@ Deletes @code{(array-ref @var{array2} (- -1 @var{k}))} from the sequence. @end table @end defun -@defun diff:edit-length array1 array2 =? p-lim +@defun diff:edit-length array1 array2 p-lim -@defunx diff:edit-length array1 array2 =? -@var{array1} and @var{array2} are one-dimensional arrays. The procedure @var{=?} is used -to compare sequence tokens for equality. + +@defunx diff:edit-length array1 array2 +@var{array1} and @var{array2} are one-dimensional arrays. The non-negative integer @var{p-lim}, if provided, is maximum number of deletions of the shorter sequence to allow. @code{diff:edit-length} will return @code{#f} @@ -91,15 +102,16 @@ if more deletions would be necessary. @code{diff:edit-length} returns the length of the shortest sequence of edits transformaing @var{array1} to @var{array2}. @end defun + @example -(diff:longest-common-subsequence "fghiejcklm" "fgehijkpqrlm" eqv?) +(diff:longest-common-subsequence "fghiejcklm" "fgehijkpqrlm") @result{} "fghijklm" -(diff:edit-length "fghiejcklm" "fgehijkpqrlm" eqv?) +(diff:edit-length "fghiejcklm" "fgehijkpqrlm") @result{} 6 -(diff:edits "fghiejcklm" "fgehijkpqrlm" eqv?) -@result{} #As32(3 -5 -7 8 9 10) +(diff:edits "fghiejcklm" "fgehijkpqrlm") +@result{} #A:fixZ32b(3 -5 -7 8 9 10) ; e c h p q r @end example |