Come calcolare la misura della similarità della distanza di 2 stringhe date?

Devo calcolare la somiglianza tra 2 stringhe. Quindi cosa intendo esattamente? Lasciatemi spiegare con un esempio:

  • La vera parola: hospital
  • Parola errata: haspita

Ora il mio objective è determinare quanti caratteri ho bisogno di modificare la parola sbagliata per ottenere la parola vera. In questo esempio, ho bisogno di modificare 2 lettere. Quindi quale sarebbe la percentuale? Prendo sempre la lunghezza della parola reale. Quindi diventa 2/8 = 25% quindi questi 2 dati DSM stringa è del 75%.

Come posso ottenere questo risultato con la prestazione che è una considerazione chiave?

    Quello che stai cercando è chiamato modifica distanza o distanza di Levenshtein . L’articolo di wikipedia spiega come viene calcolato, e ha una bella porzione di pseudocodice in basso per aiutarti a codificare questo algoritmo in C # molto facilmente.

    Ecco un’implementazione dal primo sito collegato di seguito:

     private static int CalcLevenshteinDistance(string a, string b) { if (String.IsNullOrEmpty(a) && String.IsNullOrEmpty(b)) { return 0; } if (String.IsNullOrEmpty(a)) { return b.Length; } if (String.IsNullOrEmpty(b)) { return a.Length; } 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]; } 

    Ho appena affrontato lo stesso identico problema qualche settimana fa. Dato che qualcuno sta chiedendo ora, condividerò il codice. Nei miei test approfonditi il ​​mio codice è circa 10 volte più veloce rispetto all’esempio C # su Wikipedia anche quando non viene fornita la massima distanza. Quando viene fornita una distanza massima, questo aumento di prestazioni aumenta a 30x – 100x +. Nota un paio di punti chiave per le prestazioni:

    • Se è necessario confrontare più volte le stesse parole, convertire prima le parole in matrici di interi. L’algoritmo di Damerau-Levenshtein include molti confronti>, < , == e gli ints confrontano molto più velocemente dei chars .
    • Include un meccanismo di cortocircuito per uscire se la distanza supera il massimo previsto
    • Usa un set rotante di tre array piuttosto che una matrice massiccia come in tutte le implementazioni che ho visto altrove
    • Assicurati che i tuoi array si sovrappongano alla larghezza di parole più breve.

    Codice (funziona allo stesso modo se si sostituisce int[] con String nelle dichiarazioni dei parametri:

     ///  /// 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; } 

    Dove Swap è:

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

    Esiste un grande numero di algoritmi per la distanza di similarità delle stringhe che possono essere utilizzati. Alcuni elencati qui (ma non elencati in modo esauriente sono):

    • Levenstein
    • Needleman Wunch
    • Smith Waterman
    • Smith Waterman Gotoh
    • Jaro, Jaro Winkler
    • Somiglianza Jaccard
    • Distanza euclidea
    • Somiglianza di dadi
    • Somiglianza cosina
    • Monge Elkan

    Una libreria che contiene l’implementazione di tutti questi è chiamata SimMetrics che ha implementazioni sia java che c #.

    Ho scoperto che Levenshtein e Jaro Winkler sono grandi per piccole differenze tra stringhe come:

    • Errori di ortografia; o
    • ö invece di o nel nome di una persona.

    Tuttavia, confrontando qualcosa come titoli di articoli in cui pezzi significativi del testo sarebbero uguali ma con “rumore” attorno ai bordi, Smith-Waterman-Gotoh è stato fantastico:

    confronta questi 2 titoli (che sono gli stessi ma formulati in modo diverso da fonti diverse):

    Un’endonucleasi da Escherichia coli che introduce scissioni di catene polinucleotidiche singole nel DNA irradiato con raggi ultravioletti

    Endonucleasi III: un’endonucleasi da Escherichia coli che introduce scissioni di catene polinucleotidiche singole nel DNA irradiato con ultravioletti

    Questo sito che fornisce il confronto degli algoritmi delle stringhe mostra:

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

    Jaro Winkler e Levenshtein non sono competenti quanto Smith Waterman Gotoh nel rilevare la somiglianza. Se confrontiamo due titoli che non sono lo stesso articolo, ma abbiamo un testo corrispondente:

    Metabolismo dei grassi nelle piante superiori. La funzione delle aciltioesterasi nel metabolismo degli acil-coenzimi A e della proteina carrier acil-acilica s

    Metabolismo dei grassi nelle piante superiori. La determinazione della proteina carrier acil-acilica e del coenzima acilico A in una miscela lipidica complessa

    Jaro Winkler dà un falso positivo, ma Smith Waterman Gotoh non:

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

    Come ha sottolineato Anastasiosyal , SimMetrics ha il codice java per questi algoritmi. Ho avuto successo usando il codice java SmithWatermanGotoh da SimMetrics .

    Ecco un approccio alternativo:

    Questo è troppo lungo per un commento.

    Un metodo tipico per trovare la somiglianza è la distanza di Levenshtein, e non c’è dubbio una libreria con codice disponibile.

    Sfortunatamente, ciò richiede il confronto con ogni stringa. Potresti essere in grado di scrivere una versione specializzata del codice per cortocircuitare il calcolo se la distanza è maggiore di qualche soglia, dovresti comunque fare tutti i confronti.

    Un’altra idea è di usare qualche variante di trigram o n-grammi. Queste sono sequenze di n caratteri (o n parole o n sequenze genomiche o n qualunque). Mantieni una mapping dei trigrammi alle stringhe e scegli quelle che hanno la più grande sovrapposizione. Una scelta tipica di n è “3”, da cui il nome.

    Ad esempio, l’inglese avrebbe questi trigram:

    • Eng
    • NGL
    • Gli
    • lis
    • ish

    E l’Inghilterra avrebbe:

    • Eng
    • NGL
    • gla
    • lan
    • e

    Bene, 2 su 7 (o 4 su 10) partita. Se questo funziona per te, puoi indicizzare la tabella trigram / stringa e ottenere una ricerca più veloce.

    Puoi anche combinare questo con Levenshtein per ridurre il set di confronto a quelli che hanno un numero minimo di n-grammi in comune.

    Ecco la mia implementazione di Damerau Levenshtein Distance, che restituisce non solo il coefficiente di similarità, ma restituisce anche le posizioni degli errori nella parola corretta (questa funzione può essere utilizzata negli editor di testo). Anche la mia implementazione supporta diversi pesi di errori (sostituzione, cancellazione, inserimento, trasposizione).

     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 } 

    Questo codice fa parte del mio progetto: Yandex-Linguistics.NET .

    Ho scritto alcuni test e mi sembra che il metodo stia funzionando.

    Ma i commenti e le osservazioni sono benvenuti.

    Ecco un’implementazione 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