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);