Algorítimo de comparação de Strings

ATUALIZAÇÃOEste artigo e seu código está desatualizado. Contudo, eu reescrevi ele e postei em meu novo blog:Algoritmo para comparação de strings – C# | Herbert.Lausmann

Olá,
Este é o meu primeiro post no blog. Sejam todos bem vindos.
Pois bem, este algorítimo compara duas strings e retorna um valor Double entre 0 e 100, onde 0 significa que as strings não tem nada em comum, e 100 onde as strings são totalmente iguais.


 Public Function Compare(wordA As String, wordB As String) As Double
        Dim n As Integer = wordA.Length, m As Integer = wordB.Length
        Dim distance(n + 1, m + 1) As Integer
        Dim cost As Integer = 0
        If n = 0 Then Return n
        If m = 0 Then Return m

        For i As Integer = 0 To n
            distance(i, 0) = i
        Next
        For j As Integer = 0 To m
            distance(0, j) = j
        Next
        For i As Integer = 1 To n
            For j = 1 To m
                cost = (wordB.Substring(j - 1, 1) = wordA.Substring(i - 1, 1))
                distance(i, j) = Math.Min(Math.Min(distance(i - 1, j) + 1, distance(i, j - 1) + 1), distance(i - 1, j - 1) + cost)
            Next
        Next

        Dim maxLen As Integer = wordA.Length
        If wordB.Length > wordA.Length Then
            maxLen = wordB.Length
        End If
        Dim res As Double = distance(n, m)
        res = ((1 - (res / maxLen)) / 2) * 100
        Return res
    End Function

Esse algorítimo é baseado no Algorítimo de Levenshtein. Originalmente ele foi desenvolvido para comparar palavras, mas pode ser usado tranquilamente na comparação de frases tendo somente uma perda de desempenho dependendo do tamanho da frase. Ele é muito usado por corretores ortográficos.

Este código é uma adaptação do artigo An improvement on capturing similarity between strings.