53 lines
1.3 KiB
Text
53 lines
1.3 KiB
Text
MODULE LevenshteinDistance;
|
|
FROM InOut IMPORT WriteString, WriteCard, WriteLn;
|
|
FROM Strings IMPORT Length;
|
|
|
|
PROCEDURE levenshtein(s, t: ARRAY OF CHAR): CARDINAL;
|
|
CONST MaxLen = 15;
|
|
VAR d: ARRAY [0..MaxLen],[0..MaxLen] OF CARDINAL;
|
|
lenS, lenT, i, j: CARDINAL;
|
|
|
|
PROCEDURE min(a, b: CARDINAL): CARDINAL;
|
|
BEGIN
|
|
IF a<b THEN RETURN a;
|
|
ELSE RETURN b;
|
|
END;
|
|
END min;
|
|
BEGIN
|
|
lenS := Length(s);
|
|
lenT := Length(t);
|
|
|
|
IF lenS = 0 THEN RETURN lenT;
|
|
ELSIF lenT = 0 THEN RETURN lenS;
|
|
ELSE
|
|
FOR i := 0 TO lenS DO d[i,0] := i; END;
|
|
FOR j := 0 TO lenT DO d[0,j] := j; END;
|
|
FOR i := 1 TO lenS DO
|
|
FOR j := 1 TO lenT DO
|
|
IF s[i-1] = t[j-1] THEN
|
|
d[i,j] := d[i-1,j-1];
|
|
ELSE
|
|
d[i,j] :=
|
|
min(d[i-1,j] + 1,
|
|
min(d[i,j-1] + 1, d[i-1,j-1]+1));
|
|
END;
|
|
END;
|
|
END;
|
|
RETURN d[lenS,lenT];
|
|
END;
|
|
END levenshtein;
|
|
|
|
PROCEDURE ShowDistance(s, t: ARRAY OF CHAR);
|
|
BEGIN
|
|
WriteString(s);
|
|
WriteString(" -> ");
|
|
WriteString(t);
|
|
WriteString(": ");
|
|
WriteCard(levenshtein(s, t), 0);
|
|
WriteLn();
|
|
END ShowDistance;
|
|
|
|
BEGIN
|
|
ShowDistance("kitten", "sitting");
|
|
ShowDistance("rosettacode", "raisethysword");
|
|
END LevenshteinDistance.
|