summaryrefslogtreecommitdiffstats
path: root/differ.txi
diff options
context:
space:
mode:
authorJames LewisMoss <dres@debian.org>2001-07-27 23:45:29 -0400
committerBryan Newbold <bnewbold@robocracy.org>2017-02-20 00:05:29 -0800
commitf559c149c83da84d0b1c285f0298c84aec564af9 (patch)
treef1c91bcb9bb5e6dad87b643127c3f878d80d89ee /differ.txi
parentc394920caedf3dac1981bb6b10eeb47fd6e4bb21 (diff)
parent87b82b5822ca54228cfa6df29be3ad9d4bc47d16 (diff)
downloadslib-f559c149c83da84d0b1c285f0298c84aec564af9.tar.gz
slib-f559c149c83da84d0b1c285f0298c84aec564af9.zip
Import Debian changes 2d2-1debian/2d2-1
slib (2d2-1) unstable; urgency=low * New upstream version * Revert back to free. Is now so. slib (2d1-1) unstable; urgency=low * New upstream version. * Move to non-free. FSF pointed out license doesn't allow modified versions to be distributed. * Get a complete list of copyrights that apply to the source into copyright file. * Remove setup for guile 1.3. * Remove postrm. Just calling install-info (lintian) Move install-info call to prerm since doc-base doesn't do install-info. slib (2c9-3) unstable; urgency=low * Change info location to section "The Algorithmic Language Scheme" to match up with where guile puts it's files. * Postinst is running slibconfig now. (Closes: #75891) slib (2c9-2) unstable; urgency=low * Stop installing slibconfig (for guile). * In postinst if /usr/sbin/slibconnfig exists call it (Close: #75843 #75891). slib (2c9-1) unstable; urgency=low * New upstream (Closes: #74760) * replace string-index with strsrch:string-index in http-cgi.scm. * Add doc-base support (Closes: #31163)
Diffstat (limited to 'differ.txi')
-rw-r--r--differ.txi95
1 files changed, 95 insertions, 0 deletions
diff --git a/differ.txi b/differ.txi
new file mode 100644
index 0000000..f7b1f75
--- /dev/null
+++ b/differ.txi
@@ -0,0 +1,95 @@
+@noindent
+This package implements the algorithm:
+
+@ifinfo
+@example
+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}
+@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>
+Information Processing Letters 35, 6 (1990), 317-323.
+@end ifset
+
+@noindent
+If the items being sequenced are text lines, then the computed
+edit-list is equivalent to the output of the @dfn{diff} utility
+@cindex diff
+program. If the items being sequenced are words, then it is like the
+lesser known @dfn{spiff} program.
+@cindex spiff
+
+@noindent
+The values returned by @code{diff:edit-length} can be used to gauge
+the degree of match between two sequences.
+
+@noindent
+I believe that this algorithm is currently the fastest for these
+tasks, but genome sequencing applications fuel extensive research in
+this area.
+
+
+@defun diff:longest-common-subsequence array1 array2 =?
+
+
+@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. @var{=?} defaults to @code{eqv?}.
+@code{diff:longest-common-subsequence} returns a one-dimensional array of length @code{(quotient (- (+
+len1 len2) (fp:edit-length @var{array1} @var{array2})) 2)} holding the longest sequence
+common to both @var{array}s.
+@end defun
+
+@defun diff:edits array1 array2 =?
+
+
+@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. @var{=?} defaults to @code{eqv?}.
+@code{diff:edits} returns a list of length @code{(fp:edit-length @var{array1} @var{array2})} composed of
+a shortest sequence of edits transformaing @var{array1} to @var{array2}.
+
+Each edit is a list of an integer and a symbol:
+@table @asis
+@item (@var{j} insert)
+Inserts @code{(array-ref @var{array1} @var{j})} into the sequence.
+@item (@var{k} delete)
+Deletes @code{(array-ref @var{array2} @var{k})} from the sequence.
+@end table
+@end defun
+
+@defun diff:edit-length array1 array2 =?
+
+
+@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. @var{=?} defaults to @code{eqv?}.
+@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 '#(f g h i e j c k l m)
+ '#(f g e h i j k p q r l m))
+ @result{} #(f g h i j k l m)
+
+(diff:edit-length '#(f g h i e j c k l m)
+ '#(f g e h i j k p q r l m))
+@result{} 6
+
+(pretty-print (diff:edits '#(f g h i e j c k l m)
+ '#(f g e h i j k p q r l m)))
+@print{}
+((3 insert) ; e
+ (4 delete) ; c
+ (6 delete) ; h
+ (7 insert) ; p
+ (8 insert) ; q
+ (9 insert)) ; r
+@end example
+