Jarak Levenshtein

Dalam teori informasi, linguistik, dan ilmu komputer, jarak Levenshtein adalah metrik untuk mengukur perbedaan antara dua barisan. Secara informal, jarak Levenshtein antara dua kata adalah jumlah minimum perubahan karakter (penyisipan, penghapusan, atau penggantian) yang diperlukan untuk mengubah satu kata menjadi kata lainnya. Jarak ini dinamai dengan nama matematikawan Soviet Vladimir Levenshtein, yang mempertimbangkan jarak ini pada tahun 1965.

Jarak levenshtein juga dapat disebut sebagai jarak edit, meskipun istilah tersebuh juga merujuk pada keluarga metrik jarak yang lebih umum yang dikenal secara kolektif sebagai jarak edit.

Definisi

Jarak Levenshtein antara dua string $a,b$ (yang panjangnya masing-masing $|a|$ dan $|b|$) didapatkan dengan menghitung $\operatorname {lev} (a,b)$, yang didefinisikan sebagai

$\qquad \operatorname {lev} (a,b)={\begin{cases}|a|&{\text{ jika }}|b|=0,\\|b|&{\text{ jika }}|a|=0,\\\operatorname {lev} (\operatorname {tail} (a),\operatorname {tail} (b))&{\text{ jika }}a[0]=b[0]\\1+\min {\begin{cases}\operatorname {lev} (\operatorname {tail} (a),b)\\\operatorname {lev} (a,\operatorname {tail} (b))\\\operatorname {lev} (\operatorname {tail} (a),\operatorname {tail} (b))\\\end{cases}}&{\text{ lainnya.}}\end{cases}}$

Dengan $\operatorname {tail}$ dari string $x$ adalah string dari semua kecuali karakter pertama dari $x$, dan $x[n]$ adalah karakter ke-$n$ dari string $x$, dengan $n=0$ menandakan karakter pertama. Perhatikan bahwa elemen-elemen di $\min$ secara berurutan adalah penghapusan (dari $a$ ke $b$), penyisipan, dan subtitusi. Definisi ini adalah salah bentuk definisi yang rekursif.

Contoh

matriks jarak edit untuk dua kata dengan biaya substitusi sebesar 1 dan biaya penghapusan atau penyisipan sebesar 0,5.

Sebagai contoh, jarak Levenshtein antara kata "kartun" dan kata "gantung" adalah 3, karena tiga pengeditan berikut mengubah satu kata ke kata yang lain, dan tidak ada cara untuk melakukannya dengan kurang dari tiga pengeditan:

1. kartun → gartun (substitusi "k" menjadi "g")
2. gartun → gantun (substitusi "r" menjadi "n")
3. gantun → gantung (penyisipan "g" di akhir).

Batas atas dan batas bawah

Jarak Levenshtein memiliki beberapa batas atas dan batas bawah yang sederhana. Beberapa diantaranya adalah:

• Bernilai setidaknya sebesar perbedaan ukuran kedua string tersebut.
• Maksimum bernilai sebesar panjang dari string yang lebih panjang.
• Bernilai nol jika dan hanya jika kedua string sama.
• Jika kedua string berukuran sama, jarak Hamming adalah batas atas bagi jarak Levenshtein.
• Jarak Levenshtein antara dua string tidak pernah lebih besar dari jumlah jarak Levenshtein mereka dengan suatu string lain (pertidaksamaan segitiga).

Sebuh contoh bagi jarak Levenshtein antara dua string dengan panjang yang sama, bernilai lebih kecil dari jarak Hamming, adalah pasangan kata "makan" dan "akang". Di sini jarak Levenshtein sama dengan 2 (hapus huruf "m" di awal dan sisipkan "g" di akhir), sedangkan jarak Hamming mereka sebesar 5.

Aplikasi

Dalam pencocokan string secara samar, tujuan yang ingin dicapai adalah untuk menemukan kecocokan antara sebuah string pendek dengan string lain di dalam sebuah teks yang lebih panjang; dengan anggapan hanya ada sedikit perbedaan diantara mereka. Misalnya, teks yang lebih panjang dapat berupa kamus, dan string yang pendek berasal dari masukan pengguna. Hal Ini memiliki berbagai aplikasi, misalnya untuk pemeriksa ejaan dan sistem koreksi untuk pengenalan karakter optik.

Jarak Levenshtein juga dapat dihitung antara dua string yang lebih panjang, tetapi biaya untuk menghitungnya secara kasar sebanding dengan hasil kali panjang kedua string, membuat hal ini tidak praktis. Jadi, ketika digunakan untuk membantu pencarian string samar dalam aplikasi seperti record linkage, string yang umum dibandingkan berukuran pendek untuk membantu meningkatkan kecepatan perbandingan.

Dalam linguistik, jarak Levenshtein digunakan sebagai metrik untuk mengukur jarak linguistik, atau seberapa berbedanya dua bahasa satu sama lain. Hal ini terkait dengan kejelasan timbal balik, semakin tinggi jarak linguistik, semakin rendah kejelasan timbal balik, dan semakin rendah jarak linguistik, semakin tinggi kejelasan timbal balik tersebut.

Hubungan dengan metrik jarak edit lainnya

Ada beberapa jarak edit lain yang populer, yang dihitung berdasarkan operasi-operasi edit yang diizinkan. Sebagai contoh:

• jarak Damerau-Levenshtein memperbolehkan transposisi dua karakter yang bersebelahan, di samping penyisipan, penghapusan, dan substitusi;
• jarak subbarisan terpanjang bersama (Inggris: longest common subsequence, LCS) hanya memungkinkan penyisipan dan penghapusan, namun tidak substitusi;
• jarak Hamming hanya memungkinkan substitusi, oleh karena itu, ini hanya berlaku untuk string dengan panjang yang sama.
• jarak Jaro hanya memungkinkan transposisi .

Jarak edit biasanya didefinisikan sebagai metrik yang dapat diukur parameternya yang dihitung dengan serangkaian operasi edit tertentu yang diizinkan, dan setiap operasi diberi biaya (mungkin tak terbatas). Hal ini selanjutnya digeneralisasikan oleh algoritma penyelarasan urutan DNA seperti algoritma Smith-Waterman, dengan biaya operasi bergantung pada tempat penerapannya.

Implementasi

Rekursif

Ini adalah implementasi Haskell rekursif namun tidak efisien, dari fungsi lDistance yang mengambil dua string, s dan t, bersama dengan panjangnya, dan mengembalikan jarak Levenshtein di antara keduanya:

lDistance :: ( Eq a ) => [a] -> [a] -> Int
lDistance [] t = length t   -- If s is empty the distance is the number of characters in t
lDistance s [] = length s   -- If t is empty the distance is the number of characters in s
lDistance (a:s') (b:t') =
  if
    a == b
  then
    lDistance s' t'         -- If the first characters are the same they can be ignored
  else
    1 + minimum             -- Otherwise try all three possible actions and select the best one
      [ lDistance (a:s') t' -- Character is inserted (b inserted)
      , lDistance s' (b:t') -- Character is deleted  (a deleted)
      , lDistance s' t'     -- Character is replaced (a replaced with b)
      ]

Implementasi ini sangat tidak efisien karena menghitung ulang jarak Levenshtein dari substring yang sama berkali-kali. Metode yang lebih efisien tidak mengulangi penghitungan jarak yang sama. Misalnya, dengan menyimpan jarak Levenshtein yang telah dihitung ke dalam suatu matriks $M$ dimana $M[i][j]$ adalah jarak antara yang terakhir $i$ karakter dari string s dan yang terakhir $j$ karakter string t . Matriks mudah dibuat satu baris dalam satu waktu, dimulai dengan baris 0. Ketika seluruh tabel telah selesai dibangun, jarak yang diinginkan ada pada tabel di baris dan kolom terakhir, yang merepresentasikan jarak antara semua karakter di s dan semua karakter di t.