41 lines
972 B
Plaintext
41 lines
972 B
Plaintext
' Levenshtein distance
|
|
PROGRAM "levenshtein"
|
|
|
|
DECLARE FUNCTION Entry ()
|
|
INTERNAL FUNCTION LevDist(s$, t$)
|
|
INTERNAL FUNCTION Min3(a%%, b%%, c%%)
|
|
|
|
FUNCTION Entry ()
|
|
PRINT "The Levenshtein distance..."
|
|
PRINT "between 'kitten' and 'sitting' is"; LevDist("kitten", "sitting")
|
|
PRINT "between 'rosettacode' and 'raisethysword' is"; LevDist("rosettacode", "raisethysword")
|
|
END FUNCTION
|
|
|
|
FUNCTION LevDist(s$, t$)
|
|
n%% = LEN(t$)
|
|
m%% = LEN(s$)
|
|
DIM d%%[m%%, n%%]
|
|
FOR i%% = 0 TO m%%
|
|
d%%[i%%, 0] = i%%
|
|
NEXT i%%
|
|
FOR j%% = 0 TO n%%
|
|
d%%[0, j%%] = j%%
|
|
NEXT j%%
|
|
FOR j%% = 1 TO n%%
|
|
FOR i%% = 1 TO m%%
|
|
IF s${i%% - 1} = t${j%% - 1} THEN
|
|
d%%[i%%, j%%] = d%%[i%% - 1, j%% - 1]
|
|
ELSE
|
|
d%%[i%%, j%%] = Min3(d%%[i%% - 1, j%%] + 1, d%%[i%%, j%% - 1] + 1, d%%[i%% - 1, j%% - 1] + 1)
|
|
END IF
|
|
NEXT i%%
|
|
NEXT j%%
|
|
END FUNCTION d%%[m%%, n%%]
|
|
|
|
FUNCTION Min3(a%%, b%%, c%%)
|
|
tmp%% = a%%
|
|
IF b%% < tmp%% THEN tmp%% = b%%
|
|
IF c%% < tmp%% THEN tmp%% = c%%
|
|
END FUNCTION tmp%%
|
|
END PROGRAM
|