Import Upstream version 3a2upstream/3a2

1 files changed, 36 insertions, 24 deletions

diff --git a/differ.txi b/differ.txi
index c46fc2a..247b3fe 100644
--- a/differ.txi
+++ b/differ.txi
@@ -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