Dalam teori informasi dan ilmu komputer, jarak Levenshtein adalah matriks tali untuk mengukur perbedaan antara dua sekuens. Informal, jarak Levenshtein antara dua kata adalah jumlah minimum karakter tunggal suntingan (yaitu insersi, delesi atau substitusi) diperlukan untuk mengubah satu kata ke yang lain. Hal ini dinamai Vladimir Levenshtein, yang menganggap jarak ini pada tahun 1965.
Jarak Levenshtein juga dapat disebut sebagai mengedit jarak, meskipun itu juga dapat menunjukkan lebih besar keluarga metrik jarak. Hal ini berkaitan erat dengankeberpihakan tali berpasangan .
Secara matematis, jarak Levenshtein antara dua string 
diberikan oleh 
di mana :
diberikan oleh di mana :
dimana
adalah fungsi indikator sama dengan 0 saat 
dan sama dengan 1 sebaliknya.Perhatikan bahwa elemen pertama dalam minimum sesuai dengan penghapusan (dari
untuk 
), Yang kedua untuk penyisipan dan ketiga untuk mencocokkan atau mismatch, tergantung pada apakah simbol masing-masing adalah sama.Contoh
Misalnya, jarak Levenshtein antara "kucing" dan "duduk" adalah 3, karena tiga berikut suntingan mengubah satu ke yang lain, dan tidak ada cara untuk melakukannya dengan kurang dari tiga suntingan:
- kitten → sitten (substitusi "s" untuk "k")
- sitten → sittin (substitusi "i" untuk "e")
- Sittin → sitting (penyisipan "g" di akhir).
Atas dan batas bawah
The Levenshtein jarak memiliki beberapa batas atas dan bawah sederhana. Ini termasuk:
- Itu selalu setidaknya perbedaan ukuran dari dua string.
- Hal ini paling panjang lagi tali.
- Ini adalah nol jika dan hanya jika string adalah sama.
- Jika string adalah ukuran yang sama, yang jarak Hamming adalah atas terikat pada jarak Levenshtein.
- The Levenshtein jarak antara dua string tidak lebih besar daripada jumlah jarak Levenshtein mereka dari string ketiga ( segitiga ketidaksetaraan ).
Link : Source Code Menghitung Kemiripan Dua Kalimat dengan Metode Levenshtein Distance Menggunakan VB.NET
sumber Artikel (Wikipedia)
Comments
Post a Comment