Levenshtein distance: Difference between revisions
Content added Content deleted
m (→{{header|BQN}}) |
Not a robot (talk | contribs) (Add Modula-2) |
||
Line 3,420: | Line 3,420: | ||
=={{header|Modula-2}}== |
|||
<lang modula2>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.</lang> |
|||
{{out}} |
|||
<pre>kitten -> sitting: 3 |
|||
rosettacode -> raisethysword: 8</pre> |
|||
=={{header|NetRexx}}== |
=={{header|NetRexx}}== |