Wie können wir den Damerau-Levenshtein-Abstand zwischen zwei Saiten effizient berechnen?

Berechnen Sie effizient die Ähnlichkeit der Zeichenfolgenabstände

In Anwendungen wie der Rechtschreibprüfung und der Textanalyse ist es häufig erforderlich, die Distanzähnlichkeit zwischen zwei Zeichenfolgen zu berechnen. Der Damerau-Levenshtein-Algorithmus ist eine häufig verwendete Methode, die die Anzahl der Modifikationen misst, die erforderlich sind, um eine Zeichenfolge in eine andere umzuwandeln.

Hochleistungscode-Implementierung

Um die Leistung zu optimieren, verwenden wir eine verbesserte Implementierung des Damerau-Levenshtein-Algorithmus. Es enthält die folgenden leistungssteigernden Technologien:

1. Konvertieren Sie Zeichenfolgen in Arrays von Codepunkten, um Vergleiche zu beschleunigen.
2. Durch den Kurzschlussmechanismus wird die Berechnung abgebrochen, wenn der Abstand den angegebenen Schwellenwert überschreitet.
3. Verwenden Sie drei gedrehte Arrays anstelle von Matrizen, um Array-Slicing-Vorgänge für kurze Strings zu optimieren.

Beispielcode

Der folgende Code demonstriert einen verbesserten Damerau-Levenshtein-Algorithmus, der viel schneller arbeitet als bestehende Implementierungen:

<code class="language-c#">public static int DamerauLevenshteinDistance(int[] source, int[] target, int threshold)
{
    // ... 代码略 ...

    //// 旋转数组
    dSwap = dMinus2;
    dMinus2 = dMinus1;
    dMinus1 = dCurrent;
    dCurrent = dSwap;

    int jm1 = 0, im1 = 0, im2 = -1;

    for (int j = 1; j  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;
}</code>

Leistungsüberlegungen

Die im obigen Code implementierten Leistungsverbesserungen führen zu erheblichen Geschwindigkeitsverbesserungen:

• Ungefähr zehnmal schneller als das C#-Beispiel auf Wikipedia (auch ohne die maximale Entfernungsbegrenzung).
• Bei Bereitstellung der maximalen Distanz kann der Leistungsvorteil auf das 30-fache bis 100-fache gesteigert werden.

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