starfuzz/distance

A module providing distance calculation metrics. Distance calculations compute the number of operational edits (lower values are closer) required to transform one string into another.

Types

HammingError

</>

Represents distance errors.

pub type HammingError {
  DifferentLengths
}

Constructors

```
DifferentLengths
```
Returned when the two strings compared have different lengths (Hamming requires equal lengths).

Values

hamming

</>

pub fn hamming(a: String, b: String) -> Result(Int, HammingError)

Computes the Hamming distance between two strings of equal length. Returns an error if lengths differ.

levenshtein

</>

pub fn levenshtein(a: String, b: String) -> Int

Computes the Levenshtein distance between two strings (minimum insertion, deletion, or substitution edits).

Implemented using a tail-recursive row-state optimization requiring $O(m)$ auxiliary space.

longest_common_subsequence

</>

pub fn longest_common_subsequence(a: String, b: String) -> Int

Computes the Longest Common Subsequence length (LCS) between two strings.

Implemented using a tail-recursive row-state optimization requiring $O(m)$ auxiliary space.

optimal_string_alignment

</>

pub fn optimal_string_alignment(a: String, b: String) -> Int

Computes the Optimal String Alignment (OSA / Restricted Damerau-Levenshtein) distance.

OSA computes insertions, deletions, substitutions, and adjacent transpositions, but restricts transposition edits to prevent substrings from being edited twice.

Implemented using a tail-recursive double-row carrying optimization requiring $O(m)$ auxiliary space.