Como posso medir a semelhança entre duas cordas?

Dadas duas strings text1 e text2

 public SOMEUSABLERETURNTYPE Compare(string text1, string text2) { // DO SOMETHING HERE TO COMPARE } 

Exemplos:

  1. Primeira String: StackOverflow

    Segunda Cadeia: StaqOverflow

    Retorno: a similaridade é de 91%

    O retorno pode ser em% ou algo parecido.

  2. Primeira String: O teste de texto simples

    Segunda Cadeia: O teste de texto complexo

    Retorno: os valores podem ser considerados iguais

Alguma ideia? Qual é a melhor maneira de fazer isso?

Existem várias maneiras diferentes de fazer isso. Dê uma olhada na página da Wikipedia “Medidas de similaridade de sequências” para links para outras páginas com algoritmos.

Eu não acho que nenhum desses algoritmos considere os sons, no entanto – então, “staq overflow” seria tão similar a “stack overflow” quanto “staw overflow”, apesar de o primeiro ser mais similar em termos de pronúncia.

Acabei de encontrar outra página que dá mais opções … em particular, o algoritmo Soundex ( Wikipedia ) pode estar mais perto do que você está procurando.

A distância de Levenshtein é provavelmente o que você está procurando.

Aqui está algum código que escrevi para um projeto em que estou trabalhando. Eu preciso saber a taxa de similaridade das seqüências de caracteres e a taxa de similaridade com base nas palavras das seqüências de caracteres. Este último, eu quero saber tanto o Índice de Similaridade de Palavras da menor string (então se todas as palavras existirem e corresponder na string maior o resultado será 100%) e a Razão de Similaridade das Palavras da string maior (que eu chamo RealWordsRatio ). Eu uso o algoritmo de Levenshtein para encontrar a distância. O código não está otimizado até agora, mas funciona como esperado. Espero que você ache útil.

 public static int Compute(string s, string t) { int n = s.Length; int m = t.Length; int[,] d = new int[n + 1, m + 1]; // Step 1 if (n == 0) { return m; } if (m == 0) { return n; } // Step 2 for (int i = 0; i <= n; d[i, 0] = i++) { } for (int j = 0; j <= m; d[0, j] = j++) { } // Step 3 for (int i = 1; i <= n; i++) { //Step 4 for (int j = 1; j <= m; j++) { // Step 5 int cost = (t[j - 1] == s[i - 1]) ? 0 : 1; // Step 6 d[i, j] = Math.Min( Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1), d[i - 1, j - 1] + cost); } } // Step 7 return d[n, m]; } double GetSimilarityRatio(String FullString1, String FullString2, out double WordsRatio, out double RealWordsRatio) { double theResult = 0; String[] Splitted1 = FullString1.Split(new char[]{' '}, StringSplitOptions.RemoveEmptyEntries); String[] Splitted2 = FullString2.Split(new char[]{' '}, StringSplitOptions.RemoveEmptyEntries); if (Splitted1.Length < Splitted2.Length) { String[] Temp = Splitted2; Splitted2 = Splitted1; Splitted1 = Temp; } int[,] theScores = new int[Splitted1.Length, Splitted2.Length];//Keep the best scores for each word.0 is the best, 1000 is the starting. int[] BestWord = new int[Splitted1.Length];//Index to the best word of Splitted2 for the Splitted1. for (int loop = 0; loop < Splitted1.Length; loop++) { for (int loop1 = 0; loop1 < Splitted2.Length; loop1++) theScores[loop, loop1] = 1000; BestWord[loop] = -1; } int WordsMatched = 0; for (int loop = 0; loop < Splitted1.Length; loop++) { String String1 = Splitted1[loop]; for (int loop1 = 0; loop1 < Splitted2.Length; loop1++) { String String2 = Splitted2[loop1]; int LevenshteinDistance = Compute(String1, String2); theScores[loop, loop1] = LevenshteinDistance; if (BestWord[loop] == -1 || theScores[loop, BestWord[loop]] > LevenshteinDistance) BestWord[loop] = loop1; } } for (int loop = 0; loop < Splitted1.Length; loop++) { if (theScores[loop, BestWord[loop]] == 1000) continue; for (int loop1 = loop + 1; loop1 < Splitted1.Length; loop1++) { if (theScores[loop1, BestWord[loop1]] == 1000) continue;//the worst score available, so there are no more words left if (BestWord[loop] == BestWord[loop1])//2 words have the same best word { //The first in order has the advantage of keeping the word in equality if (theScores[loop, BestWord[loop]] <= theScores[loop1, BestWord[loop1]]) { theScores[loop1, BestWord[loop1]] = 1000; int CurrentBest = -1; int CurrentScore = 1000; for (int loop2 = 0; loop2 < Splitted2.Length; loop2++) { //Find next bestword if (CurrentBest == -1 || CurrentScore > theScolors[loop1, loop2]) { CurrentBest = loop2; CurrentScore = theScolors[loop1, loop2]; } } BestWord[loop1] = CurrentBest; } else//the latter has a better score { theScolors[loop, BestWord[loop]] = 1000; int CurrentBest = -1; int CurrentScore = 1000; for (int loop2 = 0; loop2 < Splitted2.Length; loop2++) { //Find next bestword if (CurrentBest == -1 || CurrentScore > theScolors[loop, loop2]) { CurrentBest = loop2; CurrentScore = theScolors[loop, loop2]; } } BestWord[loop] = CurrentBest; } loop = -1; break;//recalculate all } } } for (int loop = 0; loop < Splitted1.Length; loop++) { if (theScores[loop, BestWord[loop]] == 1000) theResult += Splitted1[loop].Length;//All words without a score for best word are max failures else { theResult += theScores[loop, BestWord[loop]]; if (theScores[loop, BestWord[loop]] == 0) WordsMatched++; } } int theLength = (FullString1.Replace(" ", "").Length > FullString2.Replace(" ", "").Length) ? FullString1.Replace(" ", "").Length : FullString2.Replace(" ", "").Length; if(theResult > theLength) theResult = theLength; theResult = (1 - (theResult / theLength)) * 100; WordsRatio = ((double)WordsMatched / (double)Splitted2.Length) * 100; RealWordsRatio = ((double)WordsMatched / (double)Splitted1.Length) * 100; return theResult; } 

Eu escrevi uma implementação do Double Metaphone em C # há algum tempo atrás. Você vai achar muito superior ao Soundex e afins.

A distância de Levenshtein também foi sugerida, e é um ótimo algoritmo para muitos usos, mas a correspondência fonética não é realmente o que faz; só parece assim às vezes porque as palavras foneticamente similares também são soletradas de maneira similar. Eu fiz uma análise de vários algoritmos de correspondência difusa que você também pode achar útil.

Para lidar com sons semelhantes, você pode querer olhar para a codificação usando um algoritmo fonético como Double Metaphone ou soundex. Não sei se calcular distâncias de Levenshtein em cadeias codificadas fonéticas seria benéfico ou não, mas poderia ser uma possibilidade. Como alternativa, você poderia usar uma heurística como: converter cada palavra da string em sua forma codificada e remover quaisquer palavras que ocorram nas duas strings e substituí-las por uma única representação antes de calcular a distância de Levenshtein.

Você pode procurar por “distâncias” de string, por exemplo, a distância de Levenshtein .

Módulo Perl Text :: Phonetic possui implementações de vários algoritmos.

Jeff Atwood escreveu sobre a procura de uma solução semelhante para determinar a autoria de publicações wiki, o que pode ajudá-lo a restringir sua pesquisa.

Se você estiver comparando valores em um database SQL, poderá usar a function SOUNDEX . Se você consultar o Google para SOUNDEX e C #, algumas pessoas escreverão uma function semelhante para isso e para o VB.

Eu tenho que recomendar o Soundex também, eu usei no passado para processar nomes de cidades com erros ortocharts. Aqui está um bom link para o uso: http://whitepapers.zdnet.com/abstract.aspx?docid=352953

Se você quiser comparar foneticamente, confira os algoritmos Soundex e Metaphone: http://www.blackbeltcoder.com/Articles/algorithms/phonetic-string-comparison-with-soundex

O Metaphone 3 é a terceira geração do algoritmo Metaphone. Aumenta a precisão da codificação fonética de 89% do Double Metaphone para 98% , conforme testado contra um database das palavras inglesas mais comuns e nomes e palavras não inglesas familiares na América do Norte. Isso produz uma codificação fonética extremamente confiável para as pronúncias americanas.

O Metaphone 3 foi projetado e desenvolvido por Lawrence Philips, que projetou e desenvolveu os algoritmos originais Metaphone e Double Metaphone.