Berapakah jarak levenshtein?

Pengenalan

Dalam penyuntingan dokumen, mengenal pasti dan membetulkan kesilapan ejaan boleh menjadi proses manual yang membosankan. Jarak Levenshtein menawarkan penyelesaian yang canggih. Metrik ini mengukur usaha yang diperlukan untuk mengubah satu urutan ke dalam yang lain, membuktikan tidak ternilai untuk perbandingan urutan dan pembetulan kesilapan. Dinamakan selepas Vladimir Levenshtein, teknik ini merevolusikan tugas-tugas seperti penjujukan DNA dan pemeriksaan ejaan, penting dalam dunia digital yang menuntut ketepatan kami.

Mata pembelajaran utama

• Memahami konsep jarak Levenshtein dan kepentingannya.
• Perincian langkah -langkah yang terlibat dalam mengira jarak levenshtein.
• Menguasai penggunaan pengaturcaraan dinamik untuk menentukan jarak antara dua urutan.
• Sapukan pengetahuan ini kepada senario praktikal seperti pemeriksaan ejaan dan penjajaran urutan.
• Secara kritis menganalisis hasil pengiraan jarak Levenshtein dalam aplikasi dunia nyata.

Jadual Kandungan

• Berapakah jarak levenshtein dan bagaimana ia berfungsi?
  • Contoh
  • Soalan yang sering ditanya

Berapakah jarak levenshtein?

Jarak Levenshtein mengukur perbezaan antara dua urutan dengan mengira bilangan minimum suntingan yang diperlukan untuk menjadikannya sama. Penyuntingan ini termasuk:

• Penyisipan: Menambah watak.
• Penghapusan: Mengeluarkan watak.
• Penggantian: Menggantikan satu watak dengan yang lain.

Bagaimana ia berfungsi?

Mengira jarak Levenshtein menggunakan pengaturcaraan dinamik dan matriks. Prosesnya adalah seperti berikut:

Permulaan matriks

• Buat matriks di mana setiap sel (i, j) mewakili jarak antara aksara pertama I urutan A dan watak pertama J urutan B.
• Inisialisasi baris dan lajur pertama. Sel (i, 0) mewakili jarak antara aksara pertama I urutan A dan urutan kosong B (sama dengan i ). Begitu juga, (0, j) mewakili jarak antara urutan kosong A dan watak pertama J urutan B (sama dengan J ).

Populasi matriks

• Untuk setiap sel (i, j), hitung kos tiga operasi:
  • Penyisipan: Nilai Sel (I, J-1) 1
  • Penghapusan: Nilai Sel (I-1, J) 1
  • Penggantian: Nilai sel (I-1, J-1) (1 jika aksara pada kedudukan i dan j berbeza, 0 sebaliknya).
• Berikan minimum ketiga -tiga kos ini kepada sel (i, j).

Pengekstrakan keputusan

• Jarak Levenshtein adalah nilai dalam sel kanan bawah matriks.

Contoh

Mari kita hitung jarak levenshtein antara "anak kucing" dan "duduk".

Permulaan matriks

• Baris mewakili "anak kucing".
• Lajur mewakili "duduk".
• Baris dan lajur pertama diasaskan dengan indeks (mewakili penyisipan/penghapusan).

Populasi matriks

• Setiap sel dihuni berdasarkan kos minimum penyisipan, penghapusan, atau penggantian.

Pengiraan jarak

• Sel kanan bawah mengandungi jarak levenshtein terakhir.

Pengiraan terperinci

Kami bermula dengan matriks berdasarkan panjang "anak kucing" (6) dan "duduk" (7). Matriks kemudiannya dihuni menggunakan kos penyisipan, penghapusan, dan penggantian.

Matriks awal: Matriks awal dengan baris pertama dan lajur diisi kelihatan seperti ini:

Penduduk Matrix (contoh): Membandingkan 'K' (Kitten) dengan 'S' (Duduk):

• Masukkan 'K': kos = 2 (1 1)
• Padam 'S': Kos = 2 (1 1)
• Pengganti 'k' untuk 's': kos = 1 (0 1)
• Kos minimum = 1 (penggantian)

Proses ini berterusan untuk semua pasangan watak.

Tafsiran Matriks Akhir

• Baris pertama: Kos mengubah "anak kucing" ke rentetan kosong.
• Lajur Pertama: Kos Mengubah Rentetan Kosong ke "Duduk".
• Sel dalaman: Kos mengubah awalan "anak kucing" kepada awalan "duduk".

Sel kanan bawah (6,7) menunjukkan jarak levenshtein 3, yang menunjukkan tiga operasi diperlukan untuk mengubah "anak kucing" menjadi "duduk".

Kesimpulan

Jarak Levenshtein menyediakan ukuran urutan yang berharga dengan mengukur suntingan yang diperlukan untuk transformasi. Aplikasinya merangkumi pelbagai bidang, dari bioinformatik ke pemprosesan bahasa semulajadi, menjadikannya alat yang berkuasa untuk perbandingan urutan dan pembetulan kesilapan. Memahami dan menerapkan konsep ini adalah penting untuk menyelesaikan masalah dunia nyata yang melibatkan manipulasi urutan dan analisis kesamaan.

Soalan yang sering ditanya

Q1. Apakah aplikasi utama jarak Levenshtein? A. Levenshtein jarak mencari kegunaan utama dalam analisis kesamaan teks, penjujukan DNA, dan pemeriksaan ejaan untuk menilai perbezaan antara urutan.

S2. Bagaimana jarak Levenshtein dikira? A. Ia dikira menggunakan pengaturcaraan dinamik dan matriks, memandangkan penyisipan, penghapusan, dan kos penggantian.

Q3. Bolehkah levenshtein mengendalikan urutan panjang yang berbeza -beza? A. Ya, ia secara berkesan mengendalikan urutan panjang yang berbeza melalui pengiraan berasaskan matriks.

Q4. Apakah kerumitan pengiraan mengira jarak levenshtein? A. Kerumitan masa adalah O (M*n), di mana 'M' dan 'N' adalah panjang dua urutan.

Atas ialah kandungan terperinci Berapakah jarak levenshtein?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!