7.2.10 Sequence Comparison

(require 'diff)

diff:edit-length implements the algorithm:

The values returned by diff:edit-length can be used to gauge the degree of match between two sequences.

diff:edits and diff:longest-common-subsequence combine the algorithm with the divide-and-conquer method outlined in:

If the items being sequenced are text lines, then the computed edit-list is equivalent to the output of the diff utility program. If the items being sequenced are words, then it is like the lesser known spiff program.

Function: diff:longest-common-subsequence array1 array2 p-lim

Function: diff:longest-common-subsequence array1 array2

array1 and array2 are one-dimensional arrays.

The non-negative integer p-lim, if provided, is maximum number of deletions of the shorter sequence to allow. diff:longest-common-subsequence will return #f if more deletions would be necessary.

diff:longest-common-subsequence returns a one-dimensional array of length (quotient (- (+ len1 len2) (diff:edit-length array1 array2)) 2) holding the longest sequence common to both arrays.

Function: diff:edits array1 array2 p-lim

Function: diff:edits array1 array2

array1 and array2 are one-dimensional arrays.

The non-negative integer p-lim, if provided, is maximum number of deletions of the shorter sequence to allow. diff:edits will return #f if more deletions would be necessary.

diff:edits returns a vector of length (diff:edit-length array1 array2) composed of a shortest sequence of edits transformaing array1 to array2.

Each edit is an integer:

k > 0

Inserts (array-ref array1 (+ -1 j)) into the sequence.

k < 0

Deletes (array-ref array2 (- -1 k)) from the sequence.

Function: diff:edit-length array1 array2 p-lim

Function: diff:edit-length array1 array2

array1 and array2 are one-dimensional arrays.

The non-negative integer p-lim, if provided, is maximum number of deletions of the shorter sequence to allow. diff:edit-length will return #f if more deletions would be necessary.

diff:edit-length returns the length of the shortest sequence of edits transformaing array1 to array2.

(diff:longest-common-subsequence "fghiejcklm" "fgehijkpqrlm")
⇒ "fghijklm"

(diff:edit-length "fghiejcklm" "fgehijkpqrlm")
⇒ 6

(diff:edits "fghiejcklm" "fgehijkpqrlm")
⇒ #A:fixZ32b(3 -5 -7 8 9 10)
       ; e  c  h p q  r