query
On this page

levenshtein

lib.strings.levenshtein

Docs pulled from | This Revision | about 2 hours 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);