Damerau - Levenshtein -Entfernung, fügt eine Schwelle hinzu

Question

Ich habe die folgende Implementierung, aber ich möchte einen Schwellenwert hinzufügen. Wenn das Ergebnis größer sein wird als es, hören Sie einfach auf zu berechnen und kehren Sie zurück.

Wie würde ich das machen?

Bearbeiten: Hier ist mein aktueller Code, threshold wird noch nicht verwendet ... das Ziel ist, dass es verwendet wird

    public static int DamerauLevenshteinDistance(string string1, string string2, int threshold)
    {
        // Return trivial case - where they are equal
        if (string1.Equals(string2))
            return 0;

        // Return trivial case - where one is empty
        if (String.IsNullOrEmpty(string1) || String.IsNullOrEmpty(string2))
            return (string1 ?? "").Length + (string2 ?? "").Length;


        // Ensure string2 (inner cycle) is longer
        if (string1.Length > string2.Length)
        {
            var tmp = string1;
            string1 = string2;
            string2 = tmp;
        }

        // Return trivial case - where string1 is contained within string2
        if (string2.Contains(string1))
            return string2.Length - string1.Length;

        var length1 = string1.Length;
        var length2 = string2.Length;

        var d = new int[length1 + 1, length2 + 1];

        for (var i = 0; i <= d.GetUpperBound(0); i++)
            d[i, 0] = i;

        for (var i = 0; i <= d.GetUpperBound(1); i++)
            d[0, i] = i;

        for (var i = 1; i <= d.GetUpperBound(0); i++)
        {
            for (var j = 1; j <= d.GetUpperBound(1); j++)
            {
                var cost = string1[i - 1] == string2[j - 1] ? 0 : 1;

                var del = d[i - 1, j] + 1;
                var ins = d[i, j - 1] + 1;
                var sub = d[i - 1, j - 1] + cost;

                d[i, j] = Math.Min(del, Math.Min(ins, sub));

                if (i > 1 && j > 1 && string1[i - 1] == string2[j - 2] && string1[i - 2] == string2[j - 1])
                    d[i, j] = Math.Min(d[i, j], d[i - 2, j - 2] + cost);
            }
        }

        return d[d.GetUpperBound(0), d.GetUpperBound(1)];
    }
}

Answer 1

Endlich verstanden ... obwohl es nicht so vorteilhaft ist, wie ich es mir erhofft hatte

    public static int DamerauLevenshteinDistance(string string1, string string2, int threshold)
    {
        // Return trivial case - where they are equal
        if (string1.Equals(string2))
            return 0;

        // Return trivial case - where one is empty
        if (String.IsNullOrEmpty(string1) || String.IsNullOrEmpty(string2))
            return (string1 ?? "").Length + (string2 ?? "").Length;


        // Ensure string2 (inner cycle) is longer
        if (string1.Length > string2.Length)
        {
            var tmp = string1;
            string1 = string2;
            string2 = tmp;
        }

        // Return trivial case - where string1 is contained within string2
        if (string2.Contains(string1))
            return string2.Length - string1.Length;

        var length1 = string1.Length;
        var length2 = string2.Length;

        var d = new int[length1 + 1, length2 + 1];

        for (var i = 0; i <= d.GetUpperBound(0); i++)
            d[i, 0] = i;

        for (var i = 0; i <= d.GetUpperBound(1); i++)
            d[0, i] = i;

        for (var i = 1; i <= d.GetUpperBound(0); i++)
        {
            var im1 = i - 1;
            var im2 = i - 2;
            var minDistance = threshold;

            for (var j = 1; j <= d.GetUpperBound(1); j++)
            {
                var jm1 = j - 1;
                var jm2 = j - 2;
                var cost = string1[im1] == string2[jm1] ? 0 : 1;

                var del = d[im1, j] + 1;
                var ins = d[i, jm1] + 1;
                var sub = d[im1, jm1] + cost;

                //Math.Min is slower than native code
                //d[i, j] = Math.Min(del, Math.Min(ins, sub));
                d[i, j] = del <= ins && del <= sub ? del : ins <= sub ? ins : sub;

                if (i > 1 && j > 1 && string1[im1] == string2[jm2] && string1[im2] == string2[jm1])
                    d[i, j] = Math.Min(d[i, j], d[im2, jm2] + cost);

                if (d[i, j] < minDistance)
                    minDistance = d[i, j];
            }

            if (minDistance > threshold)
                return int.MaxValue;
        }

        return d[d.GetUpperBound(0), d.GetUpperBound(1)] > threshold 
            ? int.MaxValue 
            : d[d.GetUpperBound(0), d.GetUpperBound(1)];
    }

Answer 2

Dies ist in Bezug auf Ihre Antwort Folgendes: Damerau - Levenshtein -Entfernung, fügt eine Schwelle hinzu(Entschuldigung kann nicht kommentieren, da ich noch keine 50 Repräsentanten habe)

Ich denke, Sie haben hier einen Fehler gemacht. Sie haben initialisiert:

var minDistance = threshold;

Und Ihre Update -Regel lautet:

if (d[i, j] < minDistance)
   minDistance = d[i, j];

Auch Ihre frühen Ausstiegskriterien sind:

if (minDistance > threshold)
   return int.MaxValue;

Beachten Sie nun, dass der obige Bedingung niemals zutrifft! Sie sollten lieber initialisieren minDistance zu int.MaxValue

Answer 3

Hier ist der eleganteste Weg, den ich denken kann. Sehen Sie nach dem Einstellen jedes Index von D an, ob er Ihren Schwellenwert überschreitet. Die Bewertung ist konstante Zeit, daher ist es ein Abfall des Eimers im Vergleich zur theoretischen N^2 -Komplexität des Gesamtalgorithmus:

public static int DamerauLevenshteinDistance(string string1, string string2, int threshold)
{
    ...

    for (var i = 1; i <= d.GetUpperBound(0); i++)
    {
        for (var j = 1; j <= d.GetUpperBound(1); j++)
        {
            ...

            var temp = d[i,j] = Math.Min(del, Math.Min(ins, sub));

            if (i > 1 && j > 1 && string1[i - 1] == string2[j - 2] && string1[i - 2] == string2[j - 1])
                temp = d[i,j] = Math.Min(temp, d[i - 2, j - 2] + cost);

            //Does this value exceed your threshold? if so, get out now
            if(temp > threshold) 
              return temp;
        }
    }

    return d[d.GetUpperBound(0), d.GetUpperBound(1)];
}

Answer 4

Sie haben dies auch als SQL CLR UDF -Frage gestellt, also werde ich in diesem speziellen Kontext beantworten: Sie sind am besten aus der Optimierung der Levenshtein -Distanz, sondern aus der Verringerung der Anzahl der Paare, die Sie vergleichen. Ja, ein schnellerer Levenshtein -Algorithmus wird die Dinge verbessern, aber nicht annähernd so viel wie die Anzahl der Vergleiche von N Square (mit n in Millionen von Reihen) auf N*einen Faktor. Mein Vorschlag ist es, nur Elemente zu vergleichen, die den Längenunterschied innerhalb eines tolerierbaren Deltas haben. Auf Ihrer großen Tabelle fügen Sie eine persistierte berechnete Spalte hinzu LEN(Data) Erstellen Sie dann einen Index darauf mit Dateneinschluss: Daten:

ALTER TABLE Table ADD LenData AS LEN(Data) PERSISTED;
CREATE INDEX ndxTableLenData on Table(LenData) INCLUDE (Data);

Jetzt können Sie den bloßen Problemraum einschränken, indem Sie sich in einem maximalen Unterschied zu Lenght anschließen (z. B. sagen 5). Wenn Ihre Daten sind LEN(Data) variiert erheblich:

SELECT a.Data, b.Data, dbo.Levenshtein(a.Data, b.Data)
FROM Table A
JOIN Table B ON B.DataLen BETWEEN A.DataLen - 5 AND A.DataLen+5