aboutsummaryrefslogtreecommitdiffstats
path: root/differ.txi
diff options
context:
space:
mode:
authorBryan Newbold <bnewbold@robocracy.org>2017-02-20 00:05:31 -0800
committerBryan Newbold <bnewbold@robocracy.org>2017-02-20 00:05:31 -0800
commit5145dd3aa0c02c9fc496d1432fc4410674206e1d (patch)
tree540afc30c51da085f5bd8ec3f4c89f6496e7900d /differ.txi
parent8466d8cfa486fb30d1755c4261b781135083787b (diff)
downloadslib-5145dd3aa0c02c9fc496d1432fc4410674206e1d.tar.gz
slib-5145dd3aa0c02c9fc496d1432fc4410674206e1d.zip
Import Upstream version 3a2upstream/3a2
Diffstat (limited to 'differ.txi')
-rw-r--r--differ.txi60
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