Vergleicht man Strings mit Toleranz

Question

Ich bin auf der Suche nach einer Möglichkeit, eine Zeichenfolge mit einer Reihe von Zeichenfolge zu vergleichen. eine genaue Suche zu tun, ist ganz einfach, natürlich, aber ich will mein Programm tolerieren Fehler Rechtschreibung, Teile der Zeichenfolge fehlte und so weiter.

Gibt es irgendeine Art von Rahmen, die eine solche Suche durchführen können? Ich bin etwas im Auge habe, dass der Suchalgorithmus ein paar Ergebnisse, um durch den Prozentsatz der Übereinstimmung oder so etwas wie dies zurückkehren wird.

Answer 1

könnten Sie verwenden den Levenshtein Entfernung Algorithmus .

„The Levenshtein Abstand zwischen zwei Zeichenketten wird als die minimale Anzahl der Änderungen benötigt definiert eine Zeichenkette in die andere zu transformieren, wobei die zulässigen Editieroperationen wobei Insertion, Deletion oder Substitution eines einzelnen Zeichens.“ - Wikipedia.com

Dies ist von dotnetperls.com :

using System;

/// <summary>
/// Contains approximate string matching
/// </summary>
static class LevenshteinDistance
{
    /// <summary>
    /// Compute the distance between two strings.
    /// </summary>
    public static int Compute(string s, string t)
    {
        int n = s.Length;
        int m = t.Length;
        int[,] d = new int[n + 1, m + 1];

        // Step 1
        if (n == 0)
        {
            return m;
        }

        if (m == 0)
        {
            return n;
        }

        // Step 2
        for (int i = 0; i <= n; d[i, 0] = i++)
        {
        }

        for (int j = 0; j <= m; d[0, j] = j++)
        {
        }

        // Step 3
        for (int i = 1; i <= n; i++)
        {
            //Step 4
            for (int j = 1; j <= m; j++)
            {
                // Step 5
                int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;

                // Step 6
                d[i, j] = Math.Min(
                    Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
                    d[i - 1, j - 1] + cost);
            }
        }
        // Step 7
        return d[n, m];
    }
}

class Program
{
    static void Main()
    {
        Console.WriteLine(LevenshteinDistance.Compute("aunt", "ant"));
        Console.WriteLine(LevenshteinDistance.Compute("Sam", "Samantha"));
        Console.WriteLine(LevenshteinDistance.Compute("flomax", "volmax"));
    }
}

Sie können in der Tat bevorzugen den Damerau-Levenshtein Abstand verwenden Algorithmus , die auch Zeichen zu übertragen, das sind ein gemeinsamer menschlichen Fehler bei der Dateneingabe ermöglicht. Hier finden Sie eine C # -Implementierung davon finden hier .

Answer 2

Es gibt nichts in .NET Framework, die Sie mit dieser out-of-the-Box helfen.

Die häufigsten Rechtschreibfehler sind diejenigen, bei denen die Buchstaben eine anständige Laut Darstellung des Wortes, aber nicht die korrekte Schreibweise des Wortes.

Zum Beispiel könnte man argumentieren, dass die Worte sword und sord (ja, das ist ein Wort) hat die gleichen Laut Wurzeln (sie gleich klingen, wenn man sie ausspricht).

That being said, gibt es eine Reihe von Algorithmen, dass Sie Worte übersetzen können (auch falsch geschrieben ist) in Laut Varianten.

Die erste ist, Soundex . Es ist ziemlich einfach zu implementieren und es gibt eine ganze Reihe von .NET-Implementierungen dieses Algorithmus . Es ist ziemlich einfach, aber es gibt Ihnen reale Werte, die Sie miteinander vergleichen können.

Ein weiterer Grund ist Metaphone . Während ich nicht eine native .NET-Implementierung von Metaphone finden, sofern der Link hat Links zu einer Reihe von anderen Implementierungen, die umgewandelt werden könnten. Am einfachsten zu konvertieren wahrscheinlich die Java-Implementierung des Algorithmus Metaphone sein würde.

Es ist zu beachten, dass der Metaphone Algorithmus durch Revisionen gegangen ist. Es gibt Double Metaphone (die eine . NET Implementierung ) und Metaphone 3 . Metaphone 3 ist eine kommerzielle Anwendung, hat aber eine 98% Genauigkeitsrate im Vergleich zu einer 89% Genauigkeitsrate für den Double Metaphone Algorithmus, wenn gegen eine Datenbank von gemeinsamen englischen Worten laufen. Je nach Bedarf könnten Sie für aussehen soll (im Fall von Doppel Metaphone) oder Kauf (im Falle von Metaphone 3) Quelle für den Algorithmus und konvertieren oder den Zugriff darauf durch die P / Invoke Schicht (es gibt C ++ Implementierungen reichlich vorhanden).

Metaphone und Soundex unterscheiden sich in dem Sinne, dass Soundex Länge numerische Tasten befestigt erzeugt, während Metaphone Tasten verschiedener Länge erzeugt, so werden die Ergebnisse unterschiedlich. Am Ende werden beide die gleiche Art von Vergleich für Sie tun, haben, um herauszufinden, Sie nur die für Ihre Anforderungen der besten, da Ihre Anforderungen und Ressourcen (und Intoleranz Niveaus für die Rechtschreibfehler, natürlich).

Answer 3

Hier ist eine Implementierung des Levenshtein-Distanz-Methode, die weit weniger Speicher verwendet, während die gleichen Ergebnisse zu erzielen. Dies ist eine C # Anpassung des Pseudo-Code in diesem Wikipedia-Artikel unter dem „Iterative mit zwei Matrizen Zeilen“Überschrift.

public static int LevenshteinDistance(string source, string target)
{
    // degenerate cases
    if (source == target) return 0;
    if (source.Length == 0) return target.Length;
    if (target.Length == 0) return source.Length;

    // create two work vectors of integer distances
    int[] v0 = new int[target.Length + 1];
    int[] v1 = new int[target.Length + 1];

    // initialize v0 (the previous row of distances)
    // this row is A[0][i]: edit distance for an empty s
    // the distance is just the number of characters to delete from t
    for (int i = 0; i < v0.Length; i++)
        v0[i] = i;

    for (int i = 0; i < source.Length; i++)
    {
        // calculate v1 (current row distances) from the previous row v0

        // first element of v1 is A[i+1][0]
        //   edit distance is delete (i+1) chars from s to match empty t
        v1[0] = i + 1;

        // use formula to fill in the rest of the row
        for (int j = 0; j < target.Length; j++)
        {
            var cost = (source[i] == target[j]) ? 0 : 1;
            v1[j + 1] = Math.Min(v1[j] + 1, Math.Min(v0[j + 1] + 1, v0[j] + cost));
        }

        // copy v1 (current row) to v0 (previous row) for next iteration
        for (int j = 0; j < v0.Length; j++)
            v0[j] = v1[j];
    }

    return v1[target.Length];
}

Hier ist eine Funktion, die Ihnen die prozentuale Ähnlichkeit geben.

/// <summary>
/// Calculate percentage similarity of two strings
/// <param name="source">Source String to Compare with</param>
/// <param name="target">Targeted String to Compare</param>
/// <returns>Return Similarity between two strings from 0 to 1.0</returns>
/// </summary>
public static double CalculateSimilarity(string source, string target)
{
    if ((source == null) || (target == null)) return 0.0;
    if ((source.Length == 0) || (target.Length == 0)) return 0.0;
    if (source == target) return 1.0;

    int stepsToSame = LevenshteinDistance(source, target);
    return (1.0 - ((double)stepsToSame / (double)Math.Max(source.Length, target.Length)));
}

Answer 4

Die andere Option ist klanglich mit Soundex oder Metaphone zu vergleichen. Ich habe gerade einen Artikel, dass Geschenke C # Code für beide Algorithmen abgeschlossen. Sie können ihn unter http://www.blackbeltcoder.com/ Artikel / Algorithmen / Laut-String-Vergleich-mit-soundex .

Answer 5

Hier sind zwei Methoden, die die Levenshtein Entfernung zwischen Strings berechnen.

  

Die Levenshtein Abstand zwischen zwei Zeichenketten als die minimale Anzahl von Bearbeitungen definiert benötigten eine Zeichenkette in die andere zu transformieren, wobei die zulässigen Editieroperationen wobei Insertion, Deletion oder Substitution eines einzelnen Zeichens.

Wenn Sie das Ergebnis haben, werden Sie müssen definieren, was schätzen Sie wollen für ein Spiel als Schwelle verwenden oder nicht. Führen Sie die Funktion auf einer Reihe von Beispieldaten eine gute Idee davon zu bekommen, wie es funktioniert, um Hilfe zu Ihrem bestimmten Schwellenwert zu entscheiden.

    /// <summary>
    /// Calculates the Levenshtein distance between two strings--the number of changes that need to be made for the first string to become the second.
    /// </summary>
    /// <param name="first">The first string, used as a source.</param>
    /// <param name="second">The second string, used as a target.</param>
    /// <returns>The number of changes that need to be made to convert the first string to the second.</returns>
    /// <remarks>
    /// From http://www.merriampark.com/ldcsharp.htm
    /// </remarks>
    public static int LevenshteinDistance(string first, string second)
    {
        if (first == null)
        {
            throw new ArgumentNullException("first");
        }
        if (second == null)
        {
            throw new ArgumentNullException("second");
        }

        int n = first.Length;
        int m = second.Length;
        var d = new int[n + 1, m + 1]; // matrix

        if (n == 0) return m;
        if (m == 0) return n;

        for (int i = 0; i <= n; d[i, 0] = i++)
        {
        }

        for (int j = 0; j <= m; d[0, j] = j++)
        {
        }

        for (int i = 1; i <= n; i++)
        {

            for (int j = 1; j <= m; j++)
            {
                int cost = (second.Substring(j - 1, 1) == first.Substring(i - 1, 1) ? 0 : 1); // cost
                d[i, j] = Math.Min(
                    Math.Min(
                        d[i - 1, j] + 1,
                        d[i, j - 1] + 1),
                    d[i - 1, j - 1] + cost);
            }
        }

        return d[n, m];
    }

Answer 6

Sie können Implementierungen von soundex finden und die levenshtein Abstand Algorithmen in der Open-Source- CommonLibrary.NET Projekt .