Previous: , Up: Sorting and Searching   [Contents][Index]

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
```

Previous: , Up: Sorting and Searching   [Contents][Index]