The edit-distance Reference Manual

This is the edit-distance Reference Manual, version 1.0.0, generated automatically by Declt version 4.0 beta 2 "William Riker" on Sun Jan 15 04:51:55 2023 GMT+0.

Table of Contents


1 Introduction


2 Systems

The main system appears first, followed by any subsystem dependency.


2.1 edit-distance

Compute edit distance between sequences.

Author

Ben Lambert <>

License

CC-BY-4.0

Version

1.0.0

Source

edit-distance.asd.

Child Component

src (module).


3 Modules

Modules are listed depth-first from the system components tree.


3.1 edit-distance/src

Source

edit-distance.asd.

Parent Component

edit-distance (system).

Child Components

4 Files

Files are sorted by type and then listed depth-first from the systems components trees.


4.1 Lisp


4.1.1 edit-distance/edit-distance.asd

Source

edit-distance.asd.

Parent Component

edit-distance (system).

ASDF Systems

edit-distance.


4.1.2 edit-distance/src/package.lisp

Source

edit-distance.asd.

Parent Component

src (module).

Packages

edit-distance.


4.1.3 edit-distance/src/distance.lisp

Dependency

package.lisp (file).

Source

edit-distance.asd.

Parent Component

src (module).

Internals

4.1.4 edit-distance/src/interface.lisp

Dependency

distance.lisp (file).

Source

edit-distance.asd.

Parent Component

src (module).

Public Interface
Internals

4.1.5 edit-distance/src/print.lisp

Dependency

interface.lisp (file).

Source

edit-distance.asd.

Parent Component

src (module).

Internals

print-differences (function).


5 Packages

Packages are listed by definition order.


5.1 edit-distance

Source

package.lisp.

Use List

common-lisp.

Public Interface
Internals

6 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


6.1 Public Interface


6.1.1 Ordinary functions

Function: diff (s1 s2 &key test)
Package

edit-distance.

Source

interface.lisp.

Function: distance (s1 s2 &key test)
Package

edit-distance.

Source

interface.lisp.

Function: format-diff (path &key file-stream prefix1 prefix2 suffix1 suffix2)

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.

Package

edit-distance.

Source

interface.lisp.

Function: insertions-and-deletions (seq1 seq2 &key test)
Package

edit-distance.

Source

interface.lisp.

Function: print-diff (seq1 seq2 &key file-stream test prefix1 prefix2 suffix1 suffix2)

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.

Package

edit-distance.

Source

interface.lisp.


6.2 Internals


6.2.1 Ordinary functions

Function: compute-alignment (s1 s2 &key test)
Package

edit-distance.

Source

interface.lisp.

Function: compute-insertions-and-deletions (seq1 seq2 &key test)

Return a cons that points to two lists. The first is a list of the insertions; The second is a list of deletions.

Package

edit-distance.

Source

interface.lisp.

Function: edit-distance (s1 s2 &key test return-path)
Package

edit-distance.

Source

interface.lisp.

Function: get-path-from-bp-table (bp width height)

Given a back-pointer table, return a representation of the shortest path.

Package

edit-distance.

Source

distance.lisp.

Function: levenshtein-distance (s1 s2 &key test return-path)

Compute the Levenshtein distance between two sequences. If return path is t, returns the return path. O/w just returns the distance.

Package

edit-distance.

Source

distance.lisp.

Function: levenshtein-distance-fast (seq1 seq2 &key test)

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

Package

edit-distance.

Source

distance.lisp.

Function: print-differences (path &key file-stream prefix1 prefix2 suffix1 suffix2)

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.

Package

edit-distance.

Source

print.lisp.

Function: sequence-diff (seq1 seq2 &key file-stream test prefix1 prefix2 suffix1 suffix2)

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.

Package

edit-distance.

Source

interface.lisp.


Appendix A Indexes


A.1 Concepts


A.2 Functions


A.3 Variables