Rumah > pembangunan bahagian belakang > C++ > Bagaimanakah Kita Boleh Mengira Jarak Damerau-Levenshtein dengan Cekap Antara Dua Rentetan?

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

Linda Hamilton
Lepaskan: 2025-01-15 11:35:45
asal
825 orang telah melayarinya

How Can We Efficiently Calculate the Damerau-Levenshtein Distance Between Two Strings?

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;
}
Salin selepas log masuk

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!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Artikel terbaru oleh pengarang
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan