Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
This is the edit-distance Reference Manual, version 1.0.0, generated automatically by Declt version 3.0 "Montgomery Scott" on Sun May 15 03:44:53 2022 GMT+0.
• Introduction | What edit-distance is all about | |
• Systems | The systems documentation | |
• Modules | The modules documentation | |
• Files | The files documentation | |
• Packages | The packages documentation | |
• Definitions | The symbols documentation | |
• Indexes | Concepts, functions, variables and data types |
Computes the edit distance (aka Levenshtein distance) between two sequences. This is a common distance measure.
For example, to compute the distance between two sequences:
(edit-distance:distance '(1 2 3 4 5) '(2 3 4 5 6))
To compute the sequence of edit operations needed to convert sequence
1 into sequence two, use the diff
function
(edit-distance:diff '(1 2 3 4 5) '(2 3 4 5 6))
That will return two values a structure, as follows, and the distance.
((:DELETION 1 NIL) (:MATCH 2 2) (:MATCH 3 3) (:MATCH 4 4) (:MATCH 5 5) (:INSERTION NIL 6))
2
That structure can be printed more readibly with the FORMAT-DIFF
function
(edit-distance:format-diff *path*)
Or, you can compute the diff and print it readably together by calling PRINT-DIFF
:
(edit-distance:print-diff '(1 2 3 4 5) '(2 3 4 5 6))
which will print a result like this:
seq1: 1 2 3 4 5 *** []
seq2: *** 2 3 4 5 6 []
Several options are available to the FORMAT-DIFF
and PRINT-DIFF
to
print a prefix and suffix for each line. Note that displaying
substitutions relys on captialization and so substitutions are not
visible for non-alphabetic sequence elements.
Additionally, other equality functions can be used, so this evaluates to a distance of zero:
(edit-distance:distance '("ONE" "TWO" "THREE") '("one" "two"
"three") :test 'string-equal)
Any type of sequence may be used, but for speed the input sequences are copied into new arrays. If speed is a major concern make sure to provide simple vectors as your input sequences.
To test with sbcl, run:
sbcl --eval "(asdf:load-system 'edit-distance-test)" --eval "(unless (lisp-unit:run-tests :all :edit-distance-tests) (uiop:quit 1))"
cl-edit-distance by Ben Lambert is licensed under a Creative Commons Attribution 4.0 International License.
Next: Modules, Previous: Introduction, Up: Top [Contents][Index]
The main system appears first, followed by any subsystem dependency.
• The edit-distance system |
Ben Lambert <belambert@mac.com>
CC-BY-4.0
Compute edit distance between sequences.
1.0.0
edit-distance.asd (file)
src (module)
Modules are listed depth-first from the system components tree.
• The edit-distance/src module |
edit-distance (system)
src/
Files are sorted by type and then listed depth-first from the systems components trees.
• Lisp files |
• The edit-distance.asd file | ||
• The edit-distance/src/package.lisp file | ||
• The edit-distance/src/distance.lisp file | ||
• The edit-distance/src/interface.lisp file | ||
• The edit-distance/src/print.lisp file |
Next: The edit-distance/src/package․lisp file, Previous: Lisp files, Up: Lisp files [Contents][Index]
edit-distance.asd
edit-distance (system)
Next: The edit-distance/src/distance․lisp file, Previous: The edit-distance․asd file, Up: Lisp files [Contents][Index]
src (module)
src/package.lisp
Next: The edit-distance/src/interface․lisp file, Previous: The edit-distance/src/package․lisp file, Up: Lisp files [Contents][Index]
package.lisp (file)
src (module)
src/distance.lisp
Next: The edit-distance/src/print․lisp file, Previous: The edit-distance/src/distance․lisp file, Up: Lisp files [Contents][Index]
distance.lisp (file)
src (module)
src/interface.lisp
Previous: The edit-distance/src/interface․lisp file, Up: Lisp files [Contents][Index]
interface.lisp (file)
src (module)
src/print.lisp
print-differences (function)
Next: Definitions, Previous: Files, Up: Top [Contents][Index]
Packages are listed by definition order.
• The edit-distance package |
package.lisp (file)
common-lisp
Definitions are sorted by export status, category, package, and then by lexicographic order.
• Exported definitions | ||
• Internal definitions |
Next: Internal definitions, Previous: Definitions, Up: Definitions [Contents][Index]
• Exported functions |
Previous: Exported definitions, Up: Exported definitions [Contents][Index]
interface.lisp (file)
interface.lisp (file)
Print a human readable ’diff’ of the two sequences to the given stream (standard out by default). Optionally prefixes and suffixes of each line can be printed for easier identification and analysis.
interface.lisp (file)
interface.lisp (file)
Print a human readable ’diff’ of the two sequences to the given stream (standard out by default). Optionally prefixes and suffixes of each line can be printed for easier identification and analysis.
interface.lisp (file)
Previous: Exported definitions, Up: Definitions [Contents][Index]
• Internal functions |
Previous: Internal definitions, Up: Internal definitions [Contents][Index]
interface.lisp (file)
Return a cons that points to two lists. The first is a list of the insertions; The second is a list of deletions.
interface.lisp (file)
interface.lisp (file)
Given a back-pointer table, return a representation of the shortest path.
distance.lisp (file)
Compute the Levenshtein distance between two sequences. If return path is t, returns the return path. O/w just returns the distance.
distance.lisp (file)
Just like the previous version, but also return the number of *matches*.
This is pretty fast now... It looks like most of the time taken is in applying the test (e.g. string-equal)
some non-negligible part of it is taken by the MAKE-ARRAY calls and GC’ing those...
distance.lisp (file)
Given a ’path’ as produced by the above function LEVENSTEIN-DISTANCE function above,
print the differences in the format of the ’align’ program.
The prefix and suffix args allow the caller to supply a string to print before, and
after each.
print.lisp (file)
Print a human readable ’diff’ of the two sequences to the given stream (standard out by default). Optionally prefixes and suffixes of each line can be printed for easier identification and analysis.
interface.lisp (file)
Previous: Definitions, Up: Top [Contents][Index]
• Concept index | ||
• Function index | ||
• Variable index | ||
• Data type index |
Next: Function index, Previous: Indexes, Up: Indexes [Contents][Index]
Jump to: | E F L M |
---|
Jump to: | E F L M |
---|
Next: Variable index, Previous: Concept index, Up: Indexes [Contents][Index]
Jump to: | C D E F G I L P S |
---|
Jump to: | C D E F G I L P S |
---|
Next: Data type index, Previous: Function index, Up: Indexes [Contents][Index]
Previous: Variable index, Up: Indexes [Contents][Index]
Jump to: | E P S |
---|
Jump to: | E P S |
---|