46 lines
1.1 KiB
Text
46 lines
1.1 KiB
Text
'Levenshtein Distance translated by Brandon Parker
|
|
'08/19/10
|
|
'from http://www.merriampark.com/ld.htm#VB
|
|
'No credit was given to the Visual Basic Author on the site :-(
|
|
|
|
Print LevenshteinDistance("kitten", "sitting")
|
|
End
|
|
|
|
'Get the minum of three values
|
|
Function Minimum(a, b, c)
|
|
Minimum = Min(a, Min(b, c))
|
|
End Function
|
|
|
|
'Compute the Levenshtein Distance
|
|
Function LevenshteinDistance(string1$, string2$)
|
|
n = Len(string1$)
|
|
m = Len(string2$)
|
|
If n = 0 Then
|
|
LevenshteinDistance = m
|
|
Exit Function
|
|
End If
|
|
If m = 0 Then
|
|
LevenshteinDistance = n
|
|
Exit Function
|
|
End If
|
|
Dim d(n, m)
|
|
For i = 0 To n
|
|
d(i, 0) = i
|
|
Next i
|
|
For i = 0 To m
|
|
d(0, i) = i
|
|
Next i
|
|
For i = 1 To n
|
|
si$ = Mid$(string1$, i, 1)
|
|
For ii = 1 To m
|
|
tj$ = Mid$(string2$, ii, 1)
|
|
If si$ = tj$ Then
|
|
cost = 0
|
|
Else
|
|
cost = 1
|
|
End If
|
|
d(i, ii) = Minimum((d(i - 1, ii) + 1), (d(i, ii - 1) + 1), (d(i - 1, ii - 1) + cost))
|
|
Next ii
|
|
Next i
|
|
LevenshteinDistance = d(n, m)
|
|
End Function
|