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

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

holding the longest sequence common to both`array1``array2`)) 2)`array`s.

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

composed of a shortest sequence of edits transformaing`array1``array2`)`array1`to`array2`.Each edit is an integer:

`k`> 0Inserts

`(array-ref`

into the sequence.`array1`(+ -1`j`))`k`< 0Deletes

`(array-ref`

from the sequence.`array2`(- -1`k`))

- 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: String Search, Up: Sorting and Searching [Contents][Index]