Public Function LevenshteinDistance(ByVal s As String, ByVal t As String) As Integer
Dim n As Integer = s.Length
'length of s
Dim m As Integer = t.Length
'length of t
Dim d As Integer(,) = New Integer(n, m) {}
' matrix
Dim cost As Integer
' cost
' Step 1
If n = 0 Then
Return m
End If
If m = 0 Then
Return n
End If
' Step 2
Dim i As Integer = 0
While i <= n
d(i, 0) = System.Math.Max(System.Threading.Interlocked.Increment(i), i - 1)
End While
Dim j As Integer = 0
While j <= m
d(0, j) = System.Math.Max(System.Threading.Interlocked.Increment(j), j - 1)
End While
' Step 3
For o As Integer = 1 To n
'Step 4
For p As Integer = 1 To m
' Step 5
cost = (If(t.Substring(p - 1, 1) = s.Substring(o - 1, 1), 0, 1))
' Step 6
d(o, p) = System.Math.Min(System.Math.Min(d(o - 1, p) + 1, d(o, p - 1) + 1), d(o - 1, p - 1) + cost)
Next
Next
' Step 7
Return d(n, m)
End Function
|
