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

Gunakan algoritma Damerau-Levenshtein untuk mengira persamaan jarak rentetan yang diberikan

Menentukan persamaan antara rentetan adalah penting dalam pelbagai aplikasi seperti semakan ejaan dan perbandingan teks. Jarak Damerau-Levenshtein ialah ukuran cekap yang mengira bilangan minimum suntingan (sisipan, pemadaman, penggantian atau transposisi) yang diperlukan untuk mengubah satu rentetan kepada rentetan yang lain.

Pengoptimuman prestasi algoritma Damerau-Levenshtein

Untuk prestasi optimum semasa mengira jarak Damerau-Levenshtein, pertimbangkan perkara penting berikut:

• Tukar rentetan kepada tatasusunan integer: Membandingkan tatasusunan integer adalah lebih pantas daripada tatasusunan aksara.
• Mekanisme litar pintas: Jika jarak semasa melebihi ambang yang ditentukan, hentikan pengiraan.
• Putar koleksi tatasusunan: Gunakan tiga tatasusunan dan bukannya matriks besar untuk mengurangkan overhed memori.
• Optimumkan penghirisan tatasusunan: Pastikan tatasusunan sejajar dengan rentetan yang lebih pendek.

Pelaksanaan kod

Coretan kod C# yang dioptimumkan berikut melaksanakan algoritma Damerau-Levenshtein:

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

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