49 lines
1.3 KiB
Text
49 lines
1.3 KiB
Text
' FB 1.05.0 Win64
|
|
|
|
' Uses the "iterative with two matrix rows" algorithm
|
|
' referred to in the Wikipedia article.
|
|
|
|
Function min(x As Integer, y As Integer) As Integer
|
|
Return IIf(x < y, x, y)
|
|
End Function
|
|
|
|
Function levenshtein(s As String, t As String) As Integer
|
|
' degenerate cases
|
|
If s = t Then Return 0
|
|
If s = "" Then Return Len(t)
|
|
If t = "" Then Return Len(s)
|
|
|
|
' create two integer arrays of distances
|
|
Dim v0(0 To Len(t)) As Integer '' previous
|
|
Dim v1(0 To Len(t)) As Integer '' current
|
|
|
|
' initialize v0
|
|
For i As Integer = 0 To Len(t)
|
|
v0(i) = i
|
|
Next
|
|
|
|
Dim cost As Integer
|
|
For i As Integer = 0 To Len(s) - 1
|
|
' calculate v1 from v0
|
|
v1(0) = i + 1
|
|
|
|
For j As Integer = 0 To Len(t) - 1
|
|
cost = IIf(s[i] = t[j], 0, 1)
|
|
v1(j + 1) = min(v1(j) + 1, min(v0(j + 1) + 1, v0(j) + cost))
|
|
Next j
|
|
|
|
' copy v1 to v0 for next iteration
|
|
For j As Integer = 0 To Len(t)
|
|
v0(j) = v1(j)
|
|
Next j
|
|
Next i
|
|
|
|
Return v1(Len(t))
|
|
End Function
|
|
|
|
Print "'kitten' to 'sitting' => "; levenshtein("kitten", "sitting")
|
|
Print "'rosettacode' to 'raisethysword' => "; levenshtein("rosettacode", "raisethysword")
|
|
Print "'sleep' to 'fleeting' => "; levenshtein("sleep", "fleeting")
|
|
Print
|
|
Print "Press any key to quit"
|
|
Sleep
|