Come calcolare la misura di somiglianza della distanza di 2 stringhe?
-
13-11-2019 - |
Domanda
Devo calcolare la somiglianza tra 2 stringhe. Allora cosa intendo esattamente? Lasciami spiegare con un esempio:
- La vera parola:
hospital
- Parola errata:
haspita
Ora il mio obiettivo è determinare quanti personaggi ho bisogno per modificare la parola errata per ottenere la parola reale. In questo esempio, devo modificare 2 lettere. Allora quale sarebbe la percentuale? Prendo sempre la lunghezza della parola reale. Quindi diventa 2/8 = 25%, quindi questi 2 dsm di stringa forniti sono del 75%.
Come posso raggiungere questo obiettivo con le prestazioni che sono una considerazione chiave?
Soluzione
Quello che stai cercando è chiamato Modifica la distanza o Distanza di Levenshtein. L'articolo di Wikipedia spiega come viene calcolato e ha un bel pezzo di pseudocodice in fondo 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];
}
Altri suggerimenti
Ho appena affrontato lo stesso identico numero qualche settimana fa. Dal momento che qualcuno lo chiede ora, condividerò il codice. Nei miei test esaustivi il mio codice è di circa 10 volte più veloce dell'esempio C# su Wikipedia anche quando non viene fornita alcuna distanza massima. Quando viene fornita una distanza massima, questo guadagno delle prestazioni aumenta a 30x - 100x +. Nota un paio di punti chiave per le prestazioni:
- Se è necessario confrontare le stesse parole più e più volte, prima convertire le parole in array di numeri interi. L'algoritmo Damerau-Levenshtein include molti confronti
ints
confronta molto più velocemente dichars
. - Include un meccanismo di corto circuito per smettere se la distanza supera un massimo fornito
- Usa un set rotante di tre array piuttosto che una matrice enorme come in tutte le implementazioni che ho visto
- Assicurati che i tuoi array smettano la larghezza delle parole più brevi.
Codice (funziona esattamente lo stesso se si sostituisce int[]
insieme a String
Nelle dichiarazioni dei parametri:
/// <summary>
/// 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.
/// </summary>
/// <param name="source">An array of the code points of the first string</param>
/// <param name="target">An array of the code points of the second string</param>
/// <param name="threshold">Maximum allowable distance</param>
/// <returns>Int.MaxValue if threshhold exceeded; otherwise the Damerau-Leveshteim distance between the strings</returns>
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<T>(ref T arg1,ref T arg2) {
T temp = arg1;
arg1 = arg2;
arg2 = temp;
}
C'è un gran numero di algoritmi di distanza di somiglianza delle stringhe che possono essere utilizzati. Alcuni elencati qui (ma non esaustivamente elencati sono):
- Levenstein
- Needleman Wounch
- Smith Waterman
- Smith Waterman Gotoh
- Jaro, Jaro Winkler
- Jaccard Somiglianza
- Distanza euclidea
- Somiglianza dei dadi
- Somiglianza del coseno
- Monge Elkan
Una libreria che contiene l'implementazione a tutti questi è chiamata Simmetriache ha sia implementazioni Java che C#.
L'ho trovato 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, quando si confronta qualcosa come i titoli degli articoli in cui i pezzi significativi del testo sarebbero gli stessi ma con "rumore" attorno ai bordi, Smith-Waterman-Gotoh è stato fantastico:
Confronta questi 2 titoli (che sono uguali ma formulati in modo diverso da fonti diverse):
Un endonucleasi da Escherichia coli che introduce le scissioni a catena polinucleotidica singola nel DNA ultravioletto irradiato
Endonucleasi III: Un endonucleasi da Escherichia coli che introduce le scissioni a catena polinucleotidica singola nel DNA ultravioletto irradiato
Questo sito che fornisce un confronto algoritmo degli Strings Show:
- Levenshtein: 81
- Smith-Waterman Gotoh 94
- Jaro Winkler 78
Jaro Winkler e Levenshtein non sono così competenti come 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 tioesterasi aciliche nel metabolismo di acil-coenzimi A e Proteina portante acil-acileS
Metabolismo dei grassi nelle piante superiori. La determinazione di Proteina portante acil-acile e coenzima acilico A in una miscela lipidica complessa
Jaro Winkler dà un falso positivo, ma Smith Waterman Gotoh non lo fa:
- Levenshtein: 54
- Smith-Waterman Gotoh 49
- Jaro Winkler 89
Come Anastasiosyal sottolineato, Simmetria Ha il codice Java per questi algoritmi. Ho avuto successo usando il SmithwaterMangotoh Java Code di Simmetrics.
Ecco la mia implementazione della distanza di Damerau Levenshtein, che restituisce non solo il coefficiente di somiglianza, ma restituisce anche posizioni di errore in Word Corrected (questa funzione può essere utilizzata negli editori di testo). Inoltre, la mia implementazione supporta pesi diversi di errori (sostituzione, eliminazione, inserimento, trasposizione).
public static List<Mistake> 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<int, CharMistakeType>[w_length + 1, cw_length + 1];
var result = new List<Mistake>(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<int, CharMistakeType>(i, CharMistakeType.None);
for (int j = 0; j <= cw_length; j++)
d[0, j] = new KeyValuePair<int, CharMistakeType>(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<int, CharMistakeType>(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-ginguistics.net.
Ne ho scritto alcuni Test E mi sembra che il metodo funzioni.
Ma i commenti e le osservazioni sono i benvenuti.
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 una soglia, dovresti comunque fare tutti i confronti.
Un'altra idea è quella di usare una variante di trigrammi o n-grammi. Queste sono sequenze di n caratteri (o n parole o n sequenze genomiche o n qualunque). Mantieni una mappatura dei trigrammi alle stringhe e scegli quelli che hanno la più grande sovrapposizione. Una scelta tipica di N è "3", da cui il nome.
Ad esempio, l'inglese avrebbe questi trigrammi:
- Eng
- ngl
- gli
- lis
- ish
E l'Inghilterra avrebbe:
- Eng
- ngl
- gla
- Lan
- e
Bene, 2 su 7 (o 4 su 10). Se questo funziona per te e puoi indicizzare la tabella trigram/stringa e ottenere una ricerca più veloce.
Puoi anche combinarlo con Levenshtein per ridurre l'insieme di confronto con quelli che hanno un numero minimo di n-grammi in comune.
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