Como calcular a medida de similaridade de distância de duas seqüências dadas?

Eu preciso calcular a semelhança entre duas seqüências de caracteres. Então o que exatamente eu quero dizer? Deixe-me explicar com um exemplo:

  • A palavra real: hospital
  • Palavra equivocada: haspita

Agora meu objective é determinar quantos caracteres eu preciso para modificar a palavra errada para obter a palavra real. Neste exemplo, preciso modificar duas letras. Então, qual seria o percentual? Eu tomo o comprimento da palavra real sempre. Então, ele se torna 2/8 = 25%, portanto, esse DSM de duas linhas é de 75%.

Como posso conseguir isso com o desempenho sendo uma consideração importante?

O que você está procurando é chamado de distância de edição ou distância de Levenshtein . O artigo da wikipedia explica como ele é calculado e tem um bom pedaço de pseudocódigo na parte inferior para ajudá-lo a codificar este algoritmo em C # com muita facilidade.

Aqui está uma implementação do primeiro site abaixo:

 private static int CalcLevenshteinDistance(string a, string b) { if (String.IsNullOrEmpty(a) || String.IsNullOrEmpty(b)) return 0; int lengthA = a.Length; int lengthB = b.Length; var distances = new int[lengthA + 1, lengthB + 1]; for (int i = 0; i < = lengthA; distances[i, 0] = i++); for (int j = 0; j <= lengthB; distances[0, j] = j++); for (int i = 1; i <= lengthA; i++) for (int j = 1; j <= lengthB; j++) { int cost = b[j - 1] == a[i - 1] ? 0 : 1; distances[i, j] = Math.Min ( Math.Min(distances[i - 1, j] + 1, distances[i, j - 1] + 1), distances[i - 1, j - 1] + cost ); } return distances[lengthA, lengthB]; } 

Acabei de abordar esse mesmo problema há algumas semanas. Como alguém está perguntando agora, eu compartilharei o código. Em meus testes exaustivos, meu código é 10x mais rápido que o exemplo C # da Wikipédia, mesmo quando não é fornecida distância máxima. Quando uma distância máxima é fornecida, esse ganho de desempenho aumenta para 30x – 100x +. Observe alguns pontos importantes para o desempenho:

  • Se você precisar comparar as mesmas palavras repetidamente, primeiro converta as palavras em matrizes de inteiros. O algoritmo Damerau-Levenshtein inclui muitas comparações>, < , ==, e ints comparam muito mais rápido que chars .
  • Inclui um mecanismo de curto-circuito para sair se a distância exceder um máximo fornecido
  • Use um conjunto rotativo de três matrizes, em vez de uma matriz massiva, como em todas as implementações que vi em outro lugar
  • Certifique-se de que suas matrizes dividem a menor largura de palavra.

Código (funciona exatamente da mesma forma se você replace int[] por String nas declarações de parâmetro:

 ///  /// Computes the Damerau-Levenshtein Distance between two strings, represented as arrays of /// integers, where each integer represents the code point of a character in the source string. /// Includes an optional threshhold which can be used to indicate the maximum allowable distance. ///  /// An array of the code points of the first string /// An array of the code points of the second string /// Maximum allowable distance /// Int.MaxValue if threshhold exceeded; otherwise the Damerau-Leveshteim distance between the strings public static int DamerauLevenshteinDistance(int[] source, int[] target, int threshold) { int length1 = source.Length; int length2 = target.Length; // Return trivial case - difference in string lengths exceeds threshhold if (Math.Abs(length1 - length2) > threshold) { return int.MaxValue; } // Ensure arrays [i] / length1 use shorter length if (length1 > length2) { Swap(ref target, ref source); Swap(ref length1, ref length2); } int maxi = length1; int maxj = length2; int[] dCurrent = new int[maxi + 1]; int[] dMinus1 = new int[maxi + 1]; int[] dMinus2 = new int[maxi + 1]; int[] dSwap; for (int i = 0; i < = maxi; i++) { dCurrent[i] = i; } int jm1 = 0, im1 = 0, im2 = -1; for (int j = 1; j <= maxj; j++) { // Rotate dSwap = dMinus2; dMinus2 = dMinus1; dMinus1 = dCurrent; dCurrent = dSwap; // Initialize int minDistance = int.MaxValue; dCurrent[0] = j; im1 = 0; im2 = -1; for (int i = 1; i <= maxi; i++) { int cost = source[im1] == target[jm1] ? 0 : 1; int del = dCurrent[im1] + 1; int ins = dMinus1[i] + 1; int sub = dMinus1[im1] + cost; //Fastest execution for min value of 3 integers int min = (del > ins) ? (ins > sub ? sub : ins) : (del > sub ? sub : del); if (i > 1 && j > 1 && source[im2] == target[jm1] && source[im1] == target[j - 2]) min = Math.Min(min, dMinus2[im2] + cost); dCurrent[i] = min; if (min < minDistance) { minDistance = min; } im1++; im2++; } jm1++; if (minDistance > threshold) { return int.MaxValue; } } int result = dCurrent[maxi]; return (result > threshold) ? int.MaxValue : result; } 

Onde a Swap é:

 static void Swap(ref T arg1,ref T arg2) { T temp = arg1; arg1 = arg2; arg2 = temp; } 

Há um grande número de algoritmos de distância de similaridade de seqüência de caracteres que podem ser usados. Alguns listados aqui (mas não exaustivamente listados):

  • Levenstein
  • Needleman Wunch
  • Smith Waterman
  • Smith Waterman Gotoh
  • Jaro, Jaro Winkler
  • Semelhança de Jaccard
  • Distância euclidiana
  • Similaridade de dados
  • Semelhança cosseno
  • Monge Elkan

Uma biblioteca que contém implementação para todos eles é chamada SimMetrics, que possui implementações java e c #.

Eu descobri que Levenshtein e Jaro Winkler são ótimos para pequenas diferenças entre cadeias de caracteres como:

  • Erros de ortografia; ou
  • ö em vez de o no nome de uma pessoa.

No entanto, ao comparar algo como títulos de artigos em que partes significativas do texto seriam as mesmas, mas com “ruído” nas bordas, Smith-Waterman-Gotoh tem sido fantástico:

compare estes dois títulos (que são os mesmos, mas escritos diferentemente de diferentes fonts):

Uma endonuclease de Escherichia coli que introduz cisões de cadeias polinucleotídicas únicas em ADN irradiado por ultravioletas

Endonuclease III: uma Endonuclease de Escherichia coli que Introduz Cisões de Polinucleotídeo Único em DNA Ultravioleta-Irradiada

Este site que fornece comparação de algoritmo das strings mostra:

  • Levenshtein: 81
  • Smith-Waterman Gotoh 94
  • Jaro Winkler 78

Jaro Winkler e Levenshtein não são tão competentes quanto Smith Waterman Gotoh em detectar a similaridade. Se compararmos dois títulos que não são o mesmo artigo, mas temos algum texto correspondente:

Metabolismo da gordura em plantas superiores. A function das acil tioesterases no metabolismo das acil-coenzimas A e da proteína carreadora acil-acil

Metabolismo da gordura em plantas superiores. Determinação da proteína carreadora acil-acila e acil coenzima A em uma mistura lipídica complexa

Jaro Winkler dá um falso positivo, mas Smith Waterman Gotoh não:

  • Levenshtein: 54
  • Smith-Waterman Gotoh 49
  • Jaro Winkler 89

Como Anastasiosyal apontou, o SimMetrics possui o código java para esses algoritmos. Eu tive sucesso usando o código java SmithWatermanGotoh da SimMetrics .

Aqui está uma abordagem alternativa:

Isso é muito longo para um comentário.

Um método típico para encontrar similaridade é a distância de Levenshtein, e não há dúvida de que existe uma biblioteca com código disponível.

Infelizmente, isso requer comparação com todas as sequências. Você pode ser capaz de escrever uma versão especializada do código para fazer um curto-circuito no cálculo se a distância for maior que algum limite, você ainda teria que fazer todas as comparações.

Outra ideia é usar alguma variante de trigramas ou n-gramas. Estas são seqüências de n caracteres (ou n palavras ou n seqüências genômicas ou n qualquer). Mantenha um mapeamento de trigramas para seqüências de caracteres e escolha aqueles que têm a maior sobreposição. Uma escolha típica de n é “3”, daí o nome.

Por exemplo, o inglês teria esses trigramas:

  • Inglês
  • ngl
  • gli
  • lis
  • ish

E a Inglaterra teria:

  • Inglês
  • ngl
  • gla
  • lan
  • e

Bem, 2 de 7 (ou 4 de 10) correspondem. Se isso funcionar para você, você pode indexar a tabela trigram / string e obter uma pesquisa mais rápida.

Você também pode combinar isso com o Levenshtein para reduzir o conjunto de comparação com aqueles que têm um número mínimo de n-gramas em comum.

Aqui está minha implementação da Damerau Levenshtein Distance, que retorna não apenas o coeficiente de similaridade, mas também retorna localizações de erros na palavra corrigida (esse recurso pode ser usado em editores de texto). Além disso, minha implementação suporta diferentes pesos de erros (substituição, exclusão, inserção, transposição).

 public static List OptimalStringAlignmentDistance( string word, string correctedWord, bool transposition = true, int substitutionCost = 1, int insertionCost = 1, int deletionCost = 1, int transpositionCost = 1) { int w_length = word.Length; int cw_length = correctedWord.Length; var d = new KeyValuePair[w_length + 1, cw_length + 1]; var result = new List(Math.Max(w_length, cw_length)); if (w_length == 0) { for (int i = 0; i < cw_length; i++) result.Add(new Mistake(i, CharMistakeType.Insertion)); return result; } for (int i = 0; i <= w_length; i++) d[i, 0] = new KeyValuePair(i, CharMistakeType.None); for (int j = 0; j < = cw_length; j++) d[0, j] = new KeyValuePair(j, CharMistakeType.None); for (int i = 1; i < = w_length; i++) { for (int j = 1; j <= cw_length; j++) { bool equal = correctedWord[j - 1] == word[i - 1]; int delCost = d[i - 1, j].Key + deletionCost; int insCost = d[i, j - 1].Key + insertionCost; int subCost = d[i - 1, j - 1].Key; if (!equal) subCost += substitutionCost; int transCost = int.MaxValue; if (transposition && i > 1 && j > 1 && word[i - 1] == correctedWord[j - 2] && word[i - 2] == correctedWord[j - 1]) { transCost = d[i - 2, j - 2].Key; if (!equal) transCost += transpositionCost; } int min = delCost; CharMistakeType mistakeType = CharMistakeType.Deletion; if (insCost < min) { min = insCost; mistakeType = CharMistakeType.Insertion; } if (subCost < min) { min = subCost; mistakeType = equal ? CharMistakeType.None : CharMistakeType.Substitution; } if (transCost < min) { min = transCost; mistakeType = CharMistakeType.Transposition; } d[i, j] = new KeyValuePair(min, mistakeType); } } int w_ind = w_length; int cw_ind = cw_length; while (w_ind >= 0 && cw_ind >= 0) { switch (d[w_ind, cw_ind].Value) { case CharMistakeType.None: w_ind--; cw_ind--; break; case CharMistakeType.Substitution: result.Add(new Mistake(cw_ind - 1, CharMistakeType.Substitution)); w_ind--; cw_ind--; break; case CharMistakeType.Deletion: result.Add(new Mistake(cw_ind, CharMistakeType.Deletion)); w_ind--; break; case CharMistakeType.Insertion: result.Add(new Mistake(cw_ind - 1, CharMistakeType.Insertion)); cw_ind--; break; case CharMistakeType.Transposition: result.Add(new Mistake(cw_ind - 2, CharMistakeType.Transposition)); w_ind -= 2; cw_ind -= 2; break; } } if (d[w_length, cw_length].Key > result.Count) { int delMistakesCount = d[w_length, cw_length].Key - result.Count; for (int i = 0; i < delMistakesCount; i++) result.Add(new Mistake(0, CharMistakeType.Deletion)); } result.Reverse(); return result; } public struct Mistake { public int Position; public CharMistakeType Type; public Mistake(int position, CharMistakeType type) { Position = position; Type = type; } public override string ToString() { return Position + ", " + Type; } } public enum CharMistakeType { None, Substitution, Insertion, Deletion, Transposition } 

Este código é uma parte do meu projeto: Yandex-Linguistics.NET .

Eu escrevi alguns testes e parece-me que o método está funcionando.

Mas comentários e observações são bem-vindos.

Aqui está uma implementação do VB.net:

 Public Shared Function LevenshteinDistance(ByVal v1 As String, ByVal v2 As String) As Integer Dim cost(v1.Length, v2.Length) As Integer If v1.Length = 0 Then Return v2.Length 'if string 1 is empty, the number of edits will be the insertion of all characters in string 2 ElseIf v2.Length = 0 Then Return v1.Length 'if string 2 is empty, the number of edits will be the insertion of all characters in string 1 Else 'setup the base costs for inserting the correct characters For v1Count As Integer = 0 To v1.Length cost(v1Count, 0) = v1Count Next v1Count For v2Count As Integer = 0 To v2.Length cost(0, v2Count) = v2Count Next v2Count 'now work out the cheapest route to having the correct characters For v1Count As Integer = 1 To v1.Length For v2Count As Integer = 1 To v2.Length 'the first min term is the cost of editing the character in place (which will be the cost-to-date or the cost-to-date + 1 (depending on whether a change is required) 'the second min term is the cost of inserting the correct character into string 1 (cost-to-date + 1), 'the third min term is the cost of inserting the correct character into string 2 (cost-to-date + 1) and cost(v1Count, v2Count) = Math.Min( cost(v1Count - 1, v2Count - 1) + If(v1.Chars(v1Count - 1) = v2.Chars(v2Count - 1), 0, 1), Math.Min( cost(v1Count - 1, v2Count) + 1, cost(v1Count, v2Count - 1) + 1 ) ) Next v2Count Next v1Count 'the final result is the cheapest cost to get the two strings to match, which is the bottom right cell in the matrix 'in the event of strings being equal, this will be the result of zipping diagonally down the matrix (which will be square as the strings are the same length) Return cost(v1.Length, v2.Length) End If End Function