Bagaimanakah Kita Boleh Mengoptimumkan Algoritma Damerau-Levenshtein untuk Perbandingan Kesamaan Rentetan?

Perbandingan rentetan berdasarkan ukuran persamaan jarak

Pengenalan:

Dalam linguistik pengiraan dan pemprosesan bahasa semula jadi, menentukan persamaan antara dua rentetan adalah penting untuk pelbagai aplikasi. Satu metrik yang digunakan secara meluas ialah metrik persamaan jarak, yang mengukur bilangan pengubahsuaian yang diperlukan untuk mengubah satu rentetan kepada rentetan yang lain. Artikel ini bertujuan untuk menyediakan pengenalan komprehensif untuk mengira ukuran persamaan jarak antara dua rentetan yang diberikan, memfokuskan pada pengoptimuman prestasi.

Algoritma Damerau-Levenshtein:

Algoritma Damerau-Levenshtein ialah teknik yang digunakan secara meluas untuk mengira ukuran persamaan jarak antara dua rentetan. Ia mengambil kira operasi berikut: sisipan, pemadaman, penggantian dan transpose. Algoritma ini mengira bilangan minimum operasi ini yang diperlukan untuk menukar satu rentetan kepada rentetan yang lain. Sebagai contoh, jarak Damerau-Levenshtein antara "hospital" dan "haspita" ialah 2 (satu penggantian dan satu transposisi).

Pertimbangan prestasi:

Untuk aplikasi sensitif prestasi, mengoptimumkan pelaksanaan algoritma Damerau-Levenshtein adalah penting. Berikut ialah beberapa pertimbangan utama:

• Mewakili rentetan sebagai tatasusunan integer: Menukar rentetan kepada tatasusunan titik kod (integer mewakili setiap aksara) membolehkan operasi perbandingan yang lebih pantas.
• Mekanisme litar pintas: Melaksanakan mekanisme yang berhenti apabila jarak melebihi ambang yang telah ditetapkan boleh meningkatkan prestasi dengan ketara.
• Tatasusunan diputar: Menggunakan set tatasusunan diputar dan bukannya matriks besar boleh mengurangkan penggunaan memori dan meningkatkan kecekapan cache.

Pelaksanaan kod:

Kod berikut menyediakan pelaksanaan optimum algoritma Damerau-Levenshtein dalam C#:

<code class="language-c#">public static int DamerauLevenshteinDistance(int[] source, int[] target, int threshold)
{
    if (Math.Abs(source.Length - target.Length) > threshold) return int.MaxValue;
    if (source.Length > target.Length) Swap(ref target, ref source);
    int maxi = source.Length;
    int maxj = target.Length;
    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;
    for (int j = 1; j <= maxj; j++)
    {
        dMinus2 = dMinus1;
        dMinus1 = dCurrent;
        dCurrent = new int[maxi + 1];
        dCurrent[0] = j;
        for (int i = 1; i <= maxi; i++)
        {
            int cost = (source[i - 1] == target[j - 1]) ? 0 : 1;
            int del = dMinus1[i] + 1;
            int ins = dCurrent[i - 1] + 1;
            int sub = dMinus1[i - 1] + cost;
            int min = (del < ins) ? (del < sub ? del : sub) : (ins < sub ? ins : sub);
            if (i > 1 && j > 1 && source[i - 2] == target[j - 1] && source[i - 1] == target[j - 2])
                min = Math.Min(min, dMinus2[i - 2] + cost);
            dCurrent[i] = min;
            if (min > threshold) return int.MaxValue;
        }
    }
    return (dCurrent[maxi] > threshold) ? int.MaxValue : dCurrent[maxi];
}

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

Pelaksanaan ini mengikuti pertimbangan peningkatan prestasi yang digariskan sebelum ini. Dengan mewakili rentetan sebagai tatasusunan integer dan menggunakan tatasusunan diputar, ia mempercepatkan proses pengiraan dengan ketara.

Atas ialah kandungan terperinci Bagaimanakah Kita Boleh Mengoptimumkan Algoritma Damerau-Levenshtein untuk Perbandingan Kesamaan Rentetan?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!