Algoritmo para comparação de strings – C#

Olá pessoal, neste post vou apresentar um algoritmo para comparação de strings junto de uma implementação mais avançada que eu criei.

Bom, trata-se do algoritmo chamado Levenshtein-Distance, criado por um carinha chamado Vladimir Levenshtein. Segue o conceito básico do algorítimo:

Em teoria da informação, a distância Levenshtein ou distância de edição entre dois “strings” (duas sequências de caracteres) é dada pelo número mínimo de operações necessárias para transformar um string no outro. Entendemos por “operações” a inserção, deleção ou substituição de um carácter. O nome advém do cientista russo Vladimir Levenshtein, que considerou esta distância já em 1965. É muito útil para aplicações que precisam determinar quão semelhantes dois strings são, como é por exemplo o caso com os verificadores ortográficos.

Fonte: Distância Levenshtein – Wikipédia

Dado o conceito, agora irei apresentar o problema dele:

Digamos que nós temos as seguintes strings:

string a = "Herbert Lausmann";
string b = "Herbert Lausman";

string c = "Eu";
string d = "Tu";

Usando o algoritmo de Levenshtein vamos compara-las. Eis os resultados:

int ab = 1;
int cd = 1;

Perceba o seguinte: na primeira comparação o resultado foi 1 e na segunda comparação o resultado foi 1 também!

O algoritmo de Levenshtein retorna a distância entre duas strings (que no caso das duas é 1). Porém nós sabemos que ab são 50% semelhantes e cd são algo em torno de 95% semelhantes. Seria bem melhor se pudéssemos obter como resultado um valor em uma gama específica como por exemplo 0-100 onde 0 quer dizer que as strings são totalmente diferentes e 100 quer dizer que são totalmente iguais.

Pensando neste problema desenvolvi a classe estática abaixo:

using System;

namespace HL
{
    public static class HerbertLevenshteinAlgorithm
    {

        private static int LevenshteinDistance(string source, string target)
        {
            if (String.IsNullOrEmpty(source))
            {
                if (String.IsNullOrEmpty(target)) return 0;
                return target.Length;
            }
            if (String.IsNullOrEmpty(target)) return source.Length;

            if (source.Length > target.Length)
            {
                var temp = target;
                target = source;
                source = temp;
            }

            var m = target.Length;
            var n = source.Length;
            var distance = new int[2, m + 1];

            for (var j = 1; j <= m; j++) distance[0, j] = j;

            var currentRow = 0;
            for (var i = 1; i <= n; ++i)
            {
                currentRow = i & 1;
                distance[currentRow, 0] = i;
                var previousRow = currentRow ^ 1;
                for (var j = 1; j <= m; j++)
                {
                    var cost = (target[j - 1] == source[i - 1] ? 0 : 1);
                    distance[currentRow, j] = Math.Min(Math.Min(
                                distance[previousRow, j] + 1,
                                distance[currentRow, j - 1] + 1),
                                distance[previousRow, j - 1] + cost);
                }
            }
            return distance[currentRow, m];
        }

        /// <summary>
        /// Compara duas strings
        /// </summary>
        /// <param name="a">Primeira string</param>
        /// <param name="b">Segunda string</param>
        /// <returns>Retorna um valor de 0 à 255. Quanto mais alto este valor mais parecidas são as strings</returns>
        public static byte Compare(string a, string b)
        {
            double distance = LevenshteinDistance(a, b);
            if (distance == 0) return 255;
            double length = Math.Max(a.Length, b.Length);
            if (distance == length) return 0;

            double inverted = Invert(distance, length);
            byte percent = (byte)((inverted / length) * 255);
            return percent;
        }

        private static double Invert(double min, double max)
        {
            return max - min;
        }

    }
}

No caso da minha classe o método Compare(string a, string b) irá retornar um byte (com um valor de 0 à 255) onde quanto mais alto o valor mais parecidas são as strings.

Problema resolvido, agora temos um algoritmo realmente eficaz, o algoritmo de Herbert-Levenshtein. 😉

Vale citar a fonte onde eu peguei a implementação do algoritmo de Levenshtein:

Algorithm Implementation/Strings/Levenshtein distance – Wikibooks

Até mais!

Anúncios

Deixe um comentário :)

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s