Levenshtein Distance算法 也就是 “编辑距离算法”，是俄国科学家Levenshtein提出的

具体就是，一个字符串，通过加一个字符，删一个字符，替换一个字符得到另一个字串。我们把从字符串1转换成字符串2，前面3种操作用的最少次数称为12相似度

具体步骤如图所示



XXXXXt实现方法

调用Levenshtein_Distance返回相似度百分比，浮点数

Levenshtein_Distance(ByVal str1 As String, ByVal str2 As String) As Double

    Public Function Levenshtein_Distance(ByVal str1 As String, ByVal str2 As String) As Double
        Dim d As Long = 0
        Dim result As Double
        If str1.Length > str2.Length Then
            d = str1.Length
        Else
            d = str2.Length
        End If

        result = 1 - (LD(str1, str2) / d)

        Return result

    End Function

    Private Function Minimum(ByVal a As Integer, ByVal b As Integer, ByVal c As Integer) As Integer
        Dim min As Integer

        min = a
        If b < min Then
            min = b
        End If
        If c < min Then
            min = c
        End If

        Minimum = min

    End Function

    Public Function LD(ByVal s As String, ByVal t As String) As Integer
        Dim dis(,) As Integer
        Dim m As Integer
        Dim n As Integer
        Dim i As Integer
        Dim j As Integer
        Dim s_i As String
        Dim t_j As String
        Dim cost As Integer

        n = Len(s)
        m = Len(t)
        If n = 0 Then
            LD = m
            Exit Function
        End If
        If m = 0 Then
            LD = n
            Exit Function
        End If

        ReDim dis(0 To n, 0 To m)

        For i = 0 To n
            dis(i, 0) = i
        Next i

        For j = 0 To m
            dis(0, j) = j
        Next j

        For i = 1 To n

            s_i = Mid$(s, i, 1)

            For j = 1 To m

                t_j = Mid$(t, j, 1)

                If s_i = t_j Then
                    cost = 0
                Else
                    cost = 1
                End If

                dis(i, j) = Minimum(dis(i - 1, j) + 1, dis(i, j - 1) + 1, dis(i - 1, j - 1) + cost)

            Next j

        Next i

        LD = dis(n, m)
        Erase dis

    End Function