The darts.lib.sequence-metrics Reference Manual

Table of Contents

The darts.lib.sequence-metrics Reference Manual

This is the darts.lib.sequence-metrics Reference Manual, version 0.1, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 11:40:12 2018 GMT+0.

1 Introduction

DartsCLSequenceMetrics

Distance metrics on sequences in general and strings in particular.

• Constant jaro-winkler-min-prefix-length 6
• Constant jaro-winkler-prefix-adjustment-scale 1/10
• Function hamming-distance s1 s2 &key start1 end1 start2 end2 test test-not key => distance
• Function jaro-distance s1 s2 &key start1 end1 start2 end2 test test-not key => distance
• Function jaro-winkler-distance s1 s2 &key start1 end1 start2 end2 test test-not key prefix-length adjustment-scale => distance
• Function levenshein-distance s1 s2 &key start1 end1 start2 end2 test test-not key => distance
• Function list-ngrams size list &key start-padding end-padding transform => list
• Function longest-common-subsequence*-length s1 s2 &key start1 end1 start2 end2 test test-not key => length
• Function longest-common-subsequence-length s1 s2 &key start1 end1 start2 end2 test test-not key => length
• Function longest-common-subsequences* s1 s2 &key start1 end1 start2 end2 test test-not key => list
• Function longest-common-substring-length s1 s2 &key start1 end1 start2 end2 case-sensitive => length
• Function longest-common-substrings s1 s2 &key start1 end1 start2 end2 case-sensitive => list
• Function map-ngrams function size list &key start-padding end-padding
• Function string-hamming-distance s1 s2 &key start1 end1 start2 end2 case-sensitive => distance
• Function string-jaro-distance s1 s2 &key start1 end1 start2 end2 case-sensitive => distance
• Function string-jaro-winkler-distance s1 s2 &key start1 end1 start2 end2 case-sensitive prefix-length adjustment-scale => distance
• Function string-levenshtein-distance s1 s2 &key start1 end1 start2 end2 case-sensitive => distance
• Macro do-ngrams (&rest vars) (list-form &key start-padding end-padding) &body body => undefined

2 Systems

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

2.1 darts.lib.sequence-metrics

Maintainer

Dirk Esser

Author

Dirk Esser

License

MIT

Description

Provides various distance metrics on sequences

Long Description

Version

0.1

Source

darts.lib.sequence-metrics.asd (file)

Component

src (module)

3 Modules

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

3.1 darts.lib.sequence-metrics/src

Parent

darts.lib.sequence-metrics (system)

Location

src/

Components

• package.lisp (file)
• types.lisp (file)
• levenshtein.lisp (file)
• hamming.lisp (file)
• lcs.lisp (file)
• jaro-winkler.lisp (file)
• ngrams.lisp (file)

4 Files

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

4.1 Lisp

4.1.1 darts.lib.sequence-metrics.asd

Location

darts.lib.sequence-metrics.asd

Systems

darts.lib.sequence-metrics (system)

Packages

darts.asdf

4.1.2 darts.lib.sequence-metrics/src/package.lisp

Parent

src (module)

Location

src/package.lisp

Packages

darts.lib.sequence-metrics

4.1.3 darts.lib.sequence-metrics/src/types.lisp

Dependency

package.lisp (file)

Parent

src (module)

Location

src/types.lisp

Internal Definitions

• array-index (type)
• sequence-function (type)
• string-function (type)

4.1.4 darts.lib.sequence-metrics/src/levenshtein.lisp

Dependency

types.lisp (file)

Parent

src (module)

Location

src/levenshtein.lisp

Exported Definitions

• levenshtein-distance (function)
• string-levenshtein-distance (function)

4.1.5 darts.lib.sequence-metrics/src/hamming.lisp

Dependency

types.lisp (file)

Parent

src (module)

Location

src/hamming.lisp

Exported Definitions

• hamming-distance (function)
• string-hamming-distance (function)

4.1.6 darts.lib.sequence-metrics/src/lcs.lisp

Dependency

types.lisp (file)

Parent

src (module)

Location

src/lcs.lisp

Exported Definitions

• longest-common-subsequence*-length (function)
• longest-common-subsequence-length (function)
• longest-common-subsequences* (function)
• longest-common-substring-length (function)
• longest-common-substrings (function)

4.1.7 darts.lib.sequence-metrics/src/jaro-winkler.lisp

Dependency

types.lisp (file)

Parent

src (module)

Location

src/jaro-winkler.lisp

Exported Definitions

• jaro-distance (function)
• jaro-winkler-distance (function)
• string-jaro-distance (function)
• string-jaro-winkler-distance (function)

Internal Definitions

• jaro-winkler-min-prefix-length (constant)
• jaro-winkler-prefix-adjustment-scale (constant)

4.1.8 darts.lib.sequence-metrics/src/ngrams.lisp

Dependency

types.lisp (file)

Parent

src (module)

Location

src/ngrams.lisp

Exported Definitions

• do-ngrams (macro)
• list-ngrams (function)
• map-ngrams (function)

5 Packages

Packages are listed by definition order.

5.1 darts.asdf

Source

darts.lib.sequence-metrics.asd

Use List

• asdf/interface
• common-lisp

5.2 darts.lib.sequence-metrics

This package exports various forms of metric functions
on sequences. Among the ones provided are:

- Levenshtein distance
- Jaro and Jaro/Winkler distance
- Hamming distance

Most distances are provided in a very general form, working an arbitrary sequences. However, since most of these distance functions are usually applied to strings, for some frequently used metrics, optimized string versions are provided.

This package also exports a few other utility functions, which strictly speaking don’t really belong here, such as the n-gram related stuff. They live in this package, because they used to do so since the dawn of time...

Source

package.lisp (file)

Use List

common-lisp

Exported Definitions

• do-ngrams (macro)
• hamming-distance (function)
• jaro-distance (function)
• jaro-winkler-distance (function)
• levenshtein-distance (function)
• list-ngrams (function)
• longest-common-subsequence*-length (function)
• longest-common-subsequence-length (function)
• longest-common-subsequences* (function)
• longest-common-substring-length (function)
• longest-common-substrings (function)
• map-ngrams (function)
• string-hamming-distance (function)
• string-jaro-distance (function)
• string-jaro-winkler-distance (function)
• string-levenshtein-distance (function)

Internal Definitions

• array-index (type)
• jaro-winkler-min-prefix-length (constant)
• jaro-winkler-prefix-adjustment-scale (constant)
• sequence-function (type)
• string-function (type)

6 Definitions

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

6.1 Exported definitions

6.1.1 Macros

Macro: do-ngrams (&rest VARS) (LIST-FORM &key START-PADDING END-PADDING) &body BODY

Package

darts.lib.sequence-metrics

Source

ngrams.lisp (file)

6.1.2 Functions

Function: hamming-distance SEQ1 SEQ2 &key START1 END1 START2 END2 TEST TEST-NOT KEY NORMALIZED

Package

darts.lib.sequence-metrics

Source

hamming.lisp (file)

Function: jaro-distance STR1 STR2 &key START1 END1 START2 END2 TEST TEST-NOT KEY

jaro-distance SEQ1 SEQ2 &key START1 END1 START2 END2 TEST TEST-NOT KEY => DISTANCE

Package

darts.lib.sequence-metrics

Source

jaro-winkler.lisp (file)

Function: jaro-winkler-distance STR1 STR2 &key START1 END1 START2 END2 TEST TEST-NOT KEY PREFIX-LENGTH ADJUSTMENT-SCALE

Package

darts.lib.sequence-metrics

Source

jaro-winkler.lisp (file)

Function: levenshtein-distance ()

levenshtein-distance S1 S2 &key START1 END1 START2 END2 TEST TEST-NOT KEY => NUMBER

Computes the Levenshtein distance between sequences S1 and S2. The result
value DISTANCE is the minimum number of edit operations required to
transform S1 into S2 (or vice versa), where allowed operations are:

- insert a single character at some position
- delete a single character at some position
- substitute a single character at some position by another one

The Levenshtein distance is a measure of similarity between strings. If
two strings have a distance of 0, they are equal. The TEST function is
used to compare sequence elements. The default test function is eql.

This function is a generalization of string-levenshtein-distance
for arbitrary sequence types. Use string-levenshtein-distance, if you
need a version optimized for use with strings.

Package

darts.lib.sequence-metrics

Source

levenshtein.lisp (file)

Function: list-ngrams SIZE LIST &key START-PADDING END-PADDING TRANSFORM

Package

darts.lib.sequence-metrics

Source

ngrams.lisp (file)

Function: longest-common-subsequence*-length SEQ1 SEQ2 &key START1 END1 START2 END2 TEST TEST-NOT KEY

longest-common-subsequence*-length SEQ1 SEQ2 &key START1 END1 START2 END2 TEST TEST-NOT KEY => LENGTH

Returns the length of the (or: a) longest common contiguous subsequence
of sequences SEQ1 and SEQ2. This problem is usually called the longest
common ‘substring´ problem, but in order to avoid confusion, the we use the
term subsequence* here to refer to contiguous subsequences.

Package

darts.lib.sequence-metrics

Source

lcs.lisp (file)

Function: longest-common-subsequence-length SEQ1 SEQ2 &key START1 END1 START2 END2 TEST TEST-NOT KEY

Package

darts.lib.sequence-metrics

Source

lcs.lisp (file)

Function: longest-common-subsequences* SEQ1 SEQ2 &key START1 END1 START2 END2 TEST TEST-NOT KEY

longest-common-subsequences* SEQ1 SEQ2 &key START1 END1 START2 END2 TEST TEST-NOT KEY => LENGTH

Returns a list containing all contigous longest common subsequences
of SEQ1 and SEQ2. This problem is usually called the longest common
‘substring´ problem, but in order to avoid confusion, the we use the
term subsequence* here to refer to contiguous subsequences.

Package

darts.lib.sequence-metrics

Source

lcs.lisp (file)

Function: longest-common-substring-length SEQ1 SEQ2 &key START1 END1 START2 END2 CASE-SENSITIVE

Package

darts.lib.sequence-metrics

Source

lcs.lisp (file)

Function: longest-common-substrings SEQ1 SEQ2 &key START1 END1 START2 END2 CASE-SENSITIVE

Package

darts.lib.sequence-metrics

Source

lcs.lisp (file)

Function: map-ngrams FUNCTION SIZE LIST &key START-PADDING END-PADDING

map-ngrams FUNCTION N LIST &key START-PADDING END-PADDING => UNDEFINED

Calls FUNCTION for each n-gram of size N constructed from the elements in the given LIST. Initially, the value of START-PADDING is used to fill the first N - 1 elements in the call. When the list is exhausted, the value of END-PADDING is used to pad to a size of N. The function must accept N arguments.

Package

darts.lib.sequence-metrics

Source

ngrams.lisp (file)

Function: string-hamming-distance SEQ1 SEQ2 &key START1 END1 START2 END2 CASE-SENSITIVE NORMALIZED

Package

darts.lib.sequence-metrics

Source

hamming.lisp (file)

Function: string-jaro-distance ()

string-jaro-distance STR1 STR2 &key START1 END1 START2 END2 CASE-SENSITIVE => DISTANCE

Package

darts.lib.sequence-metrics

Source

jaro-winkler.lisp (file)

Function: string-jaro-winkler-distance ()

Package

darts.lib.sequence-metrics

Source

jaro-winkler.lisp (file)

Function: string-levenshtein-distance ()

string-levenshtein-distance S1 S2 &key START1 END1 START2 END2 CASE-SENSITIVE => DISTANCE

Computes the Levenshtein distance between strings S1 and S2. The result value DISTANCE is the minimum number of edit operations required to transform S1 into S2 (or vice versa), where allowed operations are:

- insert a single character at some position
- delete a single character at some position
- substitute a single character at some position by another one

The Levenshtein distance is a measure of similarity between strings. If two strings have a distance of 0, they are equal.

If CASE-SENSITIVE is true (which is the default), then comparing of characters is done in a case sensitive way, distinguishing between lower and upper case letters. If CASE-SENSITIVE is false, then this function does not distinguish between lower case and upper case letters.

See function levenshtein-distance for a generalization of this function to arbitrary sequences.

Package

darts.lib.sequence-metrics

Source

levenshtein.lisp (file)

6.2 Internal definitions

6.2.1 Constants

Constant: jaro-winkler-min-prefix-length

Package

darts.lib.sequence-metrics

Source

jaro-winkler.lisp (file)

Constant: jaro-winkler-prefix-adjustment-scale

Package

darts.lib.sequence-metrics

Source

jaro-winkler.lisp (file)

6.2.2 Types

Type: array-index ()

Integer type, which is large enough to hold an index into some arbitrary array (in particular, into a string).

Package

darts.lib.sequence-metrics

Source

types.lisp (file)

Type: sequence-function RESULT &rest ADDITIONAL-KEYS

Type of sequence metric. This function type is the essential sequence metric function type as is provided by most functions exposed by this package, if they operate on two generic sequences.

Package

darts.lib.sequence-metrics

Source

types.lisp (file)

Type: string-function RESULT &rest ADDITIONAL-KEYS

Type of string metric. This function type is the essential sequence metric function type as is provided by most functions exposed by this package, if they operate on two actual strings.

Package

darts.lib.sequence-metrics

Source

types.lisp (file)

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types