Jarak Levenshtein: Panduan Terbaik untuk Mengukur Persamaan Teks

Jarak Levenshtein, juga dikenali sebagai jarak edit, ialah metrik penting untuk menilai persamaan antara dua rentetan. Ia mengira bilangan minimum operasi yang diperlukan untuk mengubah satu rentetan kepada rentetan yang lain. Operasi ini termasuk:

1. Sisipkan: Tambahkan aksara.
2. Padam: Padamkan aksara.
3. Penggantian: Gantikan satu aksara dengan yang lain.

Konsep ini adalah teras kepada banyak aplikasi moden, seperti pembetulan ejaan, carian kabur dan perbandingan DNA.

Konsep Matematik

Jarak Levenshtein antara dua rentetan (A) dan (B) panjang (n) dan (m), masing-masing, boleh dikira menggunakan pendekatan dinamik. Kami mentakrifkan matriks (D) dimensi ((n 1) kali (m 1)), di mana setiap (D[i][j]) mewakili kos minimum untuk mengubah (i) aksara pertama (A) kepada (j) aksara pertama (B).

Formula berulang ialah:

Pelaksanaan dalam Python

Berikut ialah pelaksanaan Python mudah untuk mengira jarak Levenshtein:

def levenshtein_distance(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        for j in range(m + 1):
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            elif a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

    return dp[n][m]

# Exemple d'utilisation
print(levenshtein_distance("kitten", "sitting"))  # Sortie : 3

Aplikasi Praktikal

1. Pembetulan Ejaan

Pemeriksa ejaan menggunakan Levenshtein untuk mencadangkan perkataan rapat sekiranya berlaku kesilapan menaip. Contohnya, jika anda menaip helo, ia mungkin mencadangkan helo atau hero.

2. Carian Kabur

Dalam enjin carian, jarak Levenshtein membolehkan anda memperoleh hasil walaupun apabila pengguna membuat ralat menaip.

3. Perbandingan DNA

Dalam bioinformatik, jarak ini membantu mengukur persamaan antara dua jujukan DNA, setiap operasi mewakili kemungkinan mutasi.

4. Pengesahan dan Pengesanan Penipuan

Sistem pengesanan kecurian identiti boleh membandingkan input pengguna dengan data sedia ada, dengan mengambil kira perbezaan teks yang kecil.

Pengoptimuman: Jarak Levenshtein dengan Memori Berkurangan

Algoritma klasik menggunakan matriks penuh, yang boleh intensif memori. Nasib baik, kita boleh mengoptimumkan hanya menggunakan dua baris memori, kerana setiap pengiraan ( D[i][j] ) bergantung hanya pada ( D[i-1][j] ), ( D[i][j-1] ) , dan (D[i-1][j-1]).

def levenshtein_distance(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        for j in range(m + 1):
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            elif a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

    return dp[n][m]

# Exemple d'utilisation
print(levenshtein_distance("kitten", "sitting"))  # Sortie : 3

Kesimpulan

Jarak Levenshtein ialah alat yang berkuasa, serba boleh dan digunakan secara meluas dalam banyak bidang. Walaupun ia mudah difahami, pengoptimuman dan aplikasinya yang kompleks menunjukkan nilainya dalam sistem moden.

Menjelajah lebih jauh, kita juga boleh beralih kepada varian seperti jarak Damerau-Levenshtein, yang mengambil kira transposisi. Anda kini bersedia untuk menyepadukan alat ini ke dalam projek anda atau hanya menarik perhatian rakan sebaya anda dengan pengetahuan mendalam anda!

Adakah anda mempunyai soalan atau idea tentang jarak Levenshtein? Kongsi mereka dalam komen! ?

Atas ialah kandungan terperinci Jarak Levenshtein: Panduan Terbaik untuk Mengukur Persamaan Teks. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!