Jarak Levenshtein: Panduan Terbaik untuk Mengukur Persamaan Teks

Jarak Levenshtein, juga dikenali sebagai jarak edit, ialah metrik asas 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. Sisipan: Menambah aksara.
2. Pemadaman: Mengalih keluar aksara.
3. Penggantian: Menggantikan satu aksara dengan yang lain.

Konsep ini penting kepada banyak aplikasi moden, seperti semakan ejaan, carian kabur dan perbandingan jujukan DNA.

Konsep Matematik

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

Hubungan berulang adalah seperti berikut:

Pelaksanaan 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]

# Example usage
print(levenshtein_distance("kitten", "sitting"))  # Output: 3

Aplikasi Praktikal

1. Semakan Ejaan

Pemeriksa ejaan menggunakan jarak Levenshtein untuk mencadangkan pembetulan kesilapan silap. Contohnya, jika anda menaip helo, ia mungkin mencadangkan helo atau hero.

2. Carian Kabur

Dalam enjin carian, Levenshtein membantu mengembalikan hasil walaupun apabila pengguna membuat kesilapan taip atau ejaan.

3. Perbandingan DNA

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

4. Pengesahan dan Pengesanan Penipuan

Sistem yang mengesan penipuan identiti boleh membandingkan input pengguna dengan rekod sedia ada, mengambil kira perbezaan teks yang kecil.

Pengoptimuman: Jarak Levenshtein dengan Memori Berkurangan

Algoritma klasik menggunakan matriks penuh, yang boleh menjadi intensif memori. Nasib baik, ia boleh dioptimumkan untuk menggunakan hanya dua baris memori, kerana setiap satu ( D[i][j] ) bergantung hanya pada ( D[i-1][j] ), ( D[i][j-1] ), dan ( D[i-1][j-1] ).

def optimized_levenshtein(a, b):
    n, m = len(a), len(b)
    prev = list(range(m + 1))
    curr = [0] * (m + 1)

    for i in range(1, n + 1):
        curr[0] = i
        for j in range(1, m + 1):
            insert = curr[j - 1] + 1
            delete = prev[j] + 1
            substitute = prev[j - 1] + (0 if a[i - 1] == b[j - 1] else 1)
            curr[j] = min(insert, delete, substitute)
        prev, curr = curr, prev

    return prev[m]

# Example usage
print(optimized_levenshtein("kitten", "sitting"))  # Output: 3

Kesimpulan

Jarak Levenshtein ialah alat yang berkuasa dan serba boleh digunakan secara meluas dalam pelbagai bidang. Walaupun mudah untuk difahami, pengoptimuman dan aplikasi kompleksnya menyerlahkan nilainya dalam sistem moden.

Untuk penerokaan lanjut, pertimbangkan varian seperti jarak Damerau-Levenshtein, yang merangkumi transposisi. Anda kini bersedia untuk menyepadukan alat ini ke dalam projek anda atau menarik perhatian rakan sebaya anda dengan pemahaman mendalam anda!

Ada 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!