Come calcolare la misura di somiglianza della distanza di 2 stringhe?

StackOverflow https://stackoverflow.com/questions/9453731

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?

È stato utile?

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 di chars.
  • 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):

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
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top