Damerau Levenshtein Algorithm by R.G.

Damerau Levenshtein Algorithm by R.G..

'**************************************
' Name: Damerau Levenshtein Algorithm
' Description:This function returns the 
'     Levenshtein distance capped by the limit
'     parameter.
' By: R.G.
'
'
' Inputs:None
'
' Returns:None
'
'Assumes:None
'
'Side Effects:None
'This code is copyrighted and has limite
'     d warranties.
'Please see http://www.Planet-Source-Cod
'     e.com/xq/ASP/txtCodeId.71576/lngWId.1/qx
'     /vb/scripts/ShowCode.htm
'for details.
'**************************************

'Debug.Print damerau_levenshtein("Alexan
'     der (2004)", "Alexander", 10)

Function damerau_levenshtein(s1 As String, s2 As String, Optional limit As Variant, Optional result As Variant) As Integer
    'This function returns the Levenshtein d
    '     istance capped by the limit parameter.

    Dim diagonal As Integer
    Dim horizontal As Integer
    Dim vertical As Integer
    Dim swap As Integer
    Dim final As Integer

    'set a maximum limit if not set

    If IsMissing(limit) Then
        limit = Len(s1) + Len(s2)
    End If

    'create the result matrix to store inter
    '     mediary results

    If IsMissing(result) Then
        Dim i, j As Integer ' pointeur
        ReDim result(Len(s1), Len(s2)) As Integer
    End If

    'Start of the strings analysis

    If result(Len(s1), Len(s2)) < 1 Then

        If Abs(Len(s1) - Len(s2)) >= limit Then
            final = limit
        Else

            If Len(s1) = 0 Or Len(s2) = 0 Then
                'End of recursivity
                final = Len(s1) + Len(s2)
            Else

                'Core of levenshtein algorithm

                If Mid(s1, 1, 1) = Mid(s2, 1, 1) Then
                    final = damerau_levenshtein(Mid(s1, 2), Mid(s2, 2), limit, result)
                Else

                    If Mid(s1, 1, 1) = Mid(s2, 2, 1) And Mid(s1, 2, 1) = Mid(s2, 1, 1) Then
                        'Damerau extension counting swapped lett
                        '     ers
                        swap = damerau_levenshtein(Mid(s1, 3), Mid(s2, 3), limit - 1, result)
                        final = 1 + swap
                    Else
                        'The function minimum is implemented via
                        '     the limit parameter.
                        'The diagonal search usually reaches the
                        '     limit the quickest.
                        diagonal = damerau_levenshtein(Mid(s1, 2), Mid(s2, 2), limit - 1, result)
                        horizontal = damerau_levenshtein(Mid(s1, 2), s2, diagonal, result)
                        vertical = damerau_levenshtein(s1, Mid(s2, 2), horizontal, result)
                        final = 1 + vertical
                    End If
                End If

            End If
        End If
    Else
        'retrieve intermediate result
        final = result(Len(s1), Len(s2)) - 1
    End If

    'returns the distance capped by the limi
    '     t

    If final < limit Then
        damerau_levenshtein = final
        'store intermediate result
        result(Len(s1), Len(s2)) = final + 1
    Else
        damerau_levenshtein = limit
    End If

End Function
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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s