Bagaimanakah Kita Boleh Mengira Jarak Damerau-Levenshtein dengan Cekap Antara Dua Rentetan?

Mengira persamaan jarak rentetan dengan cekap

Dalam aplikasi seperti semakan ejaan dan analisis teks, selalunya perlu untuk mengira persamaan jarak antara dua rentetan. Algoritma Damerau-Levenshtein ialah kaedah yang biasa digunakan yang mengukur bilangan pengubahsuaian yang diperlukan untuk mengubah satu rentetan kepada rentetan yang lain.

Pelaksanaan kod prestasi tinggi

Untuk mengoptimumkan prestasi, kami menggunakan pelaksanaan algoritma Damerau-Levenshtein yang dipertingkatkan. Ia mengandungi teknologi peningkatan prestasi berikut:

1. Tukar rentetan kepada tatasusunan titik kod untuk mempercepatkan perbandingan.
2. Menggunakan mekanisme litar pintas, pengiraan akan ditamatkan jika jarak melebihi ambang yang ditetapkan.
3. Gunakan tiga tatasusunan diputar dan bukannya matriks untuk mengoptimumkan operasi penghirisan tatasusunan untuk rentetan pendek.

Kod sampel

Kod berikut menunjukkan algoritma Damerau-Levenshtein yang dipertingkatkan yang berprestasi lebih pantas daripada pelaksanaan sedia ada:

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;
}

Pertimbangan Prestasi

Peningkatan prestasi yang dilaksanakan dalam kod di atas menghasilkan peningkatan kelajuan yang ketara:

• Kira-kira 10 kali lebih pantas daripada contoh C# di Wikipedia (walaupun tanpa had jarak maksimum).
• Apabila jarak maksimum disediakan, kelebihan prestasi boleh ditingkatkan kepada 30 kali ganda hingga 100 kali ganda.

Atas ialah kandungan terperinci Bagaimanakah Kita Boleh Mengira Jarak Damerau-Levenshtein dengan Cekap Antara Dua Rentetan?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!