Wie kann ich den Damerau-Levenshtein-Abstand zwischen zwei Saiten effizient berechnen?

Verwenden Sie den Damerau-Levenshtein-Algorithmus, um die Distanzähnlichkeit einer bestimmten Zeichenfolge zu berechnen

Die Bestimmung der Ähnlichkeit zwischen Zeichenfolgen ist in einer Vielzahl von Anwendungen wie der Rechtschreibprüfung und dem Textvergleich von entscheidender Bedeutung. Der Damerau-Levenshtein-Abstand ist ein effizientes Maß, das die Mindestanzahl an Bearbeitungen (Einfügungen, Löschungen, Ersetzungen oder Transpositionen) berechnet, die erforderlich sind, um eine Zeichenfolge in eine andere umzuwandeln.

Leistungsoptimierung des Damerau-Levenshtein-Algorithmus

Berücksichtigen Sie für eine optimale Leistung bei der Berechnung der Damerau-Levenshtein-Distanz die folgenden wichtigen Punkte:

• Konvertieren Sie eine Zeichenfolge in ein Array von Ganzzahlen: Der Vergleich von Arrays aus Ganzzahlen ist viel schneller als der Vergleich von Arrays aus Zeichen.
• Kurzschlussmechanismus: Wenn der aktuelle Abstand den angegebenen Schwellenwert überschreitet, wird die Berechnung gestoppt.
• Sammlung von Arrays rotieren: Verwenden Sie drei Arrays anstelle großer Matrizen, um den Speicheraufwand zu reduzieren.
• Array-Slicing optimieren: Stellen Sie sicher, dass Arrays an kürzeren Zeichenfolgen ausgerichtet sind.

Code-Implementierung

Der folgende optimierte C#-Codeausschnitt implementiert den Damerau-Levenshtein-Algorithmus:

public static int DamerauLevenshteinDistance(int[] source, int[] target, int threshold) {
    int length1 = source.Length;
    int length2 = target.Length;

    if (Math.Abs(length1 - length2) > threshold) { return int.MaxValue; }

    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  1 && j > 1 && source[im2] == target[jm1] && source[im1] == target[j - 2])
                min = Math.Min(min, dMinus2[im2] + cost);
            dCurrent[i] = min;
            if (min  threshold) { return int.MaxValue; }
    }

    int result = dCurrent[maxi];
    return (result > threshold) ? int.MaxValue : result;
}

Das obige ist der detaillierte Inhalt vonWie kann ich den Damerau-Levenshtein-Abstand zwischen zwei Saiten effizient berechnen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!