levenshtein

lib.strings.levenshtein

Docs pulled from | This Revision | about 1 hour ago

Computes the Levenshtein distance between two strings a and b.

Complexity O(n*m) where n and m are the lengths of the strings. Algorithm adjusted from https://stackoverflow.com/a/9750974/6605742

Inputs

a: 1. Function argument
b: 2. Function argument

Type

levenshtein :: string -> string -> int

Examples

`lib.strings.levenshtein` usage example

levenshtein "foo" "foo"
=> 0
levenshtein "book" "hook"
=> 1
levenshtein "hello" "Heyo"
=> 3

Noogle detected

Implementation

The following is the current implementation of this function.

levenshtein =
    a: b:
    let
      # Two dimensional array with dimensions (stringLength a + 1, stringLength b + 1)
      arr = lib.genList (i: lib.genList (j: dist i j) (stringLength b + 1)) (stringLength a + 1);
      d = x: y: lib.elemAt (lib.elemAt arr x) y;
      dist =
        i: j:
        let
          c = if substring (i - 1) 1 a == substring (j - 1) 1 b then 0 else 1;
        in
        if j == 0 then
          i
        else if i == 0 then
          j
        else
          lib.min (lib.min (d (i - 1) j + 1) (d i (j - 1) + 1)) (d (i - 1) (j - 1) + c);
    in
    d (stringLength a) (stringLength b);