Levenshtein Distance in VBA

Levenshtein Distance in VBA/Excel

Option Explicit
PublicFunction Levenshtein(s1 AsString, s2 AsString)

Dim i AsInteger
Dim j AsInteger
Dim l1 AsInteger
Dim l2 AsInteger
Dim d()AsInteger
Dim min1 AsInteger
Dim min2 AsInteger

l1 = Len(s1)
l2 = Len(s2)
ReDim d(l1, l2)
For i =0To l1
    d(i,0)= i
Next
For j =0To l2
    d(0, j)= j
Next
For i =1To l1
    For j =1To l2
        If Mid(s1, i,1)= Mid(s2, j,1)Then
            d(i, j)= d(i -1, j -1)
        Else
            min1 = d(i -1, j)+1
            min2 = d(i, j -1)+1
            If min2 < min1 Then
                min1 = min2
            EndIf
            min2 = d(i -1, j -1)+1
            If min2 < min1 Then
                min1 = min2
            EndIf
            d(i, j)= min1
        EndIf
    Next
Next
Levenshtein = d(l1, l2)
EndFunction

Version 2

Function Levenshtein(ByVal string1 AsString,ByVal string2 AsString)AsLong

Dim i AsLong, j AsLong
Dim string1_length AsLong
Dim string2_length AsLong
Dim distance()AsLong

string1_length = Len(string1)
string2_length = Len(string2)
ReDim distance(string1_length, string2_length)

For i =0To string1_length
    distance(i,0)= i
Next

For j =0To string2_length
    distance(0, j)= j
Next

For i =1To string1_length
    For j =1To string2_length
        If Asc(Mid$(string1, i,1))= Asc(Mid$(string2, j,1))Then
            distance(i, j)= distance(i -1, j -1)
        Else
            distance(i, j)= Application.WorksheetFunction.Min _
            (distance(i -1, j)+1, _
             distance(i, j -1)+1, _
             distance(i -1, j -1)+1)
        EndIf
    Next
Next

Levenshtein = distance(string1_length, string2_length)

EndFunction

 

 

 

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s