21 lines
720 B
Text
21 lines
720 B
Text
import <Utilities/Sequence.sl>;
|
|
import <Utilities/Math.sl>;
|
|
|
|
main(args(2)) := LenenshteinDistance(args[1], args[2]);
|
|
|
|
LenenshteinDistance(s(1), t(1)) :=
|
|
0 when equalList(s,t) else
|
|
size(t) when size(s) = 0 else
|
|
size(s) when size(t) = 0 else
|
|
LenenshteinDistanceIterative(s, t, 0 ... size(t), duplicate(0, size(t) + 1), 1);
|
|
|
|
LenenshteinDistanceIterative(s(1), t(1), v0(1), v1(1), n) :=
|
|
v0[size(t) + 1] when n > size(s) else
|
|
LenenshteinDistanceIterative(s, t, iterate(s[n], t, v0, setElementAt(v1, 1, n + 0), 1), v0, n + 1);
|
|
|
|
iterate(s, t(1), v0(1), v1(1), n) :=
|
|
v1 when n > size(t) else
|
|
iterate(s, t, v0,
|
|
setElementAt(v1, n + 1,
|
|
min(min(v1[n] + 1, v0[n + 1] + 1), v0[n] + (0 when s = t[n] else 1))),
|
|
n + 1);
|