c# - ¿Cómo calcular la medida de similitud de distancia de 2 cadenas dadas?

.net levenshtein-distance

Question

Necesito calcular la similitud entre 2 cadenas. Entonces, ¿qué quiero decir exactamente? Dejame explicarte con un ejemplo:

• La palabra real: hospital
• Palabra equivocada: haspita

Ahora mi objetivo es determinar cuántos caracteres necesito para modificar la palabra equivocada y obtener la palabra real. En este ejemplo, necesito modificar 2 letras. Entonces, ¿cuál sería el porcentaje? Tomo la longitud de la palabra real siempre. Entonces se convierte en 2/8 = 25%, por lo que estos 2 DSM de cuerda dados son 75%.

¿Cómo puedo lograr esto con el rendimiento siendo una consideración clave?

Answer 1

Acabo de abordar este mismo problema hace unas semanas. Como alguien está preguntando ahora, compartiré el código. En mis exhaustivas pruebas, mi código es aproximadamente 10 veces más rápido que el ejemplo de C # en Wikipedia, incluso cuando no se proporciona una distancia máxima. Cuando se proporciona una distancia máxima, esta ganancia de rendimiento aumenta a 30x - 100x +. Tenga en cuenta un par de puntos clave para el rendimiento:

• Si necesita comparar las mismas palabras una y otra vez, primero convierta las palabras en matrices de enteros. El algoritmo de Damerau-Levenshtein incluye muchas comparaciones>, <, == y las comparaciones mucho más rápidas que los chars .
• Incluye un mecanismo de cortocircuito para salir si la distancia excede un máximo proporcionado
• Use un conjunto rotativo de tres matrices en lugar de una matriz masiva como en todas las implementaciones que he visto en otro lugar
• Asegúrate de que tus matrices crucen el ancho de palabra más corto.

Código (funciona exactamente igual si reemplaza int[] con String en las declaraciones de parámetros:

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

Donde Swap es:

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

Answer 2

Aquí está mi implementación de Damerau Levenshtein Distance, que devuelve no solo el coeficiente de similitud, sino que también devuelve las ubicaciones de error en la palabra corregida (esta característica se puede usar en los editores de texto). También mi implementación admite diferentes pesos de errores (sustitución, eliminación, inserción, transposición).

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
}

Este código es parte de mi proyecto: Yandex-Linguistics.NET .

Escribí algunas tests y me parece que el método está funcionando.

Pero los comentarios y comentarios son bienvenidos.

Answer 3

Aquí hay un enfoque alternativo:

Esto es demasiado largo para un comentario.

Un método típico para encontrar similitud es la distancia de Levenshtein, y no hay duda de que hay una biblioteca con código disponible.

Desafortunadamente, esto requiere una comparación con cada cadena. Es posible que pueda escribir una versión especializada del código para provocar un cortocircuito en el cálculo, si la distancia es mayor que algún umbral, aún tendría que hacer todas las comparaciones.

Otra idea es usar alguna variante de trigramas o n-gramas. Estas son secuencias de n caracteres (o n palabras o n secuencias genómicas o n lo que sea). Mantenga un mapeo de trigramas en cadenas y elija los que tienen la mayor superposición. Una elección típica de n es "3", de ahí el nombre.

Por ejemplo, el inglés tendría estos trigramas:

• Eng
• ngl
• gli
• lis
• ish

E Inglaterra tendría:

• Eng
• ngl
• gla
• lan
• y

Bueno, 2 de 7 (o 4 de 10) coinciden. Si esto funciona para usted, puede indexar la tabla trigram / string y obtener una búsqueda más rápida.

También puede combinar esto con Levenshtein para reducir el conjunto de comparación a aquellos que tienen un número mínimo de n-grams en común.

Answer 4

Aquí hay una implementación de 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

Answer 5

Hay una gran cantidad de algoritmos de distancia de similitud de cadenas que se pueden usar. Algunas de las enumeradas aquí (pero no se enumeran exhaustivamente) son:

• Levenstein
• Needleman Wunch
• Smith Waterman
• Smith Waterman Gotoh
• Jaro, Jaro Winkler
• Similitud de Jaccard
• Distancia euclidiana
• Dados Similitud
• Similitud Coseno
• Monge Elkan

Una biblioteca que contiene la implementación de todos estos se llama SimMetrics que tiene implementaciones tanto java como c #.

Answer 6

He descubierto que Levenshtein y Jaro Winkler son geniales para pequeñas diferencias entre cadenas como:

• Faltas de ortografía; o
• ö en lugar de o en el nombre de una persona.

Sin embargo, cuando comparamos algo así como títulos de artículos donde fragmentos significativos del texto serían los mismos pero con "ruido" en los bordes, Smith-Waterman-Gotoh ha sido fantástico:

compare estos 2 títulos (que son iguales pero están redactados de forma diferente a partir de diferentes fuentes):

Una endonucleasa de Escherichia coli que introduce una sola cadena de polinucleótidos en el ADN irradiado con radiación ultravioleta

Endonucleasa III: una endonucleasa de Escherichia coli que presenta las secuencias de cadena de polinucleótidos individuales en el ADN irradiado con radiación ultravioleta

Este sitio que proporciona una comparación de algoritmo de las cadenas muestra:

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

Jaro Winkler y Levenshtein no son tan competentes como Smith Waterman Gotoh en la detección de la similitud. Si comparamos dos títulos que no son el mismo artículo, pero tienen algún texto coincidente:

metabolismo de las grasas en las plantas superiores. La función de las acil tioesterasas en el metabolismo de las acil-coenzimas A y la proteína transportadora de acil-acilo

metabolismo de las grasas en las plantas superiores. La determinación de la proteína transportadora de acil-acilo y la acil coenzima A en una mezcla de lípidos complejos

Jaro Winkler da un falso positivo, pero Smith Waterman Gotoh no:

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

Como señaló, SimMetrics tiene el código java para estos algoritmos. Tuve éxito usando el código JavaWatermanGotoh de SimMetrics .

Answer 7

Lo que estás buscando se llama distancia de edición o distancia de Levenshtein . El artículo de wikipedia explica cómo se calcula, y tiene una buena pieza de pseudocódigo en la parte inferior para ayudarte a codificar este algoritmo en C # muy fácilmente.

Aquí hay una implementación del primer sitio vinculado a continuación:

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