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   -- Jika s kosong maka jarak adalah banyak karakter di t
lDistance s [] = length s   -- Jika t kosong maka jarak adalah banyak karakter di s
lDistance (a:s') (b:t') =
  if
    a == b
  then
    lDistance s' t'         -- Jika karakter pertama mereka sama maka dapat diabaikan
  else
    1 + minimum             -- Untuk kasus lain, cari nilai minimum dari tiga aksi ini
      [ lDistance (a:s') t' -- Karakter disisipkan  (b disisipkan)
      , lDistance s' (b:t') -- Karakter dihapus     (a dihapus)
      , lDistance s' t'     -- Karakter disubtitusi (a diganti dengan 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.

Iteratif dengan matriks

Menghitung jarak Levenshtein yang lebih efisien didasarkan pada pengamatan bahwa jika kita menyimpan matriks untuk mencatat jarak Levenshtein antara semua awalan dari string pertama dan semua awalan pada string kedua, maka kita dapat menghitung nilai-nilai dalam matriks dalam bentuk pemrograman dinamis, sehingga jarak antara dua string penuh sebagai elemen terakhir yang dihitung.

Algoritma ini, contoh dari pemrograman dinamis tipe bottom-up, dibahas dalam artikel 1974 "The String-to-string correction problem" oleh Robert A. Wagner dan Michael J. Fischer. Berikut ini adalah implementasi pseudocode untuk fungsi LevenshteinDistance yang mengambil dua string, s dengan panjang m, dan t dengan panjang n, dan mengembalikan jarak Levenshtein di antara keduanya:

function LevenshteinDistance(char s[1..m], char t[1..n]):
  // untuk setiap i and j, d[i,j] akan menyimpan jarak Levenshtein distance antara
  // i karakter pertama dari s dan j karakter pertama dari t
  declare int d[0..m, 0..n]
 
  set each element in d to zero
 
  // awalan di sumber dapat diubah menjadi string kosong
  // dengan menghapus semua karakter
  for i from 1 to m:
      d[i, 0] := i
 
  // awalan di target dapat dicapai dari awalan berupa string kosong
  // dengan menyisipkan semua karakter
  for j from 1 to n:
      d[0, j] := j
 
  for j from 1 to n:
      for i from 1 to m:
          if s[i] = t[j]:
            substitutionCost := 0
          else:
            substitutionCost := 1

          d[i, j] := minimum(d[i-1, j] + 1,                   // penghapusan
                             d[i, j-1] + 1,                   // penyisipan
                             d[i-1, j-1] + substitutionCost)  // subtitusi
 
  return d[m, n]

Dua contoh matriks yang dihasilkan (mengarahkan kursor ke nomor yang diberi tag akan mengungkapkan operasi yang dilakukan untuk mendapatkan nomor tersebut):

		k	i	t	t	e	n
	0	1	2	3	4	5	6
s	1	1	2	3	4	5	6
i	2	2	1	2	3	4	5
t	3	3	2	1	2	3	4
t	4	4	3	2	1	2	3
i	5	5	4	3	2	2	3
n	6	6	5	4	3	3	2
g	7	7	6	5	4	4	3

		S	a	t	u	r	d	a	y
	0	1	2	3	4	5	6	7	8
S	1	0	1	2	3	4	5	6	7
u	2	1	1	2	2	3	4	5	6
n	3	2	2	2	3	3	4	5	6
d	4	3	3	3	3	4	3	4	5
a	5	4	3	4	4	4	4	3	4
y	6	5	4	4	5	5	5	4	3

Iteratif dengan dua baris matriks

Pada pengamatan lebih lanjut, hanya dua baris matriks yang diperlukan untuk menghitung jarak Levenshtein; jika tidak ingin merekonstruksi string input yang diedit. Jarak Levenshtein dapat dihitung secara iteratif menggunakan algoritma berikut:

function LevenshteinDistance(char s[0..m-1], char t[0..n-1]):
    // bentuk dua vektor kerja dengan jarak integer
    declare int v0[n + 1]
    declare int v1[n + 1]

    // inisialisasi v0 (baris jarak sebelumnya)
    // Baris ini setara dengan A[0][i]: jarak edit bagi s yang kosong
    // Jaraknya cuma banyaknya karakter yang perlu dihapus dari t
    for i from 0 to n:
        v0[i] = i

    for i from 0 to m-1:
        // hitung v1 (baris jarak saat ini) dari baris v0 sebelumnya

        // elemen pertama v1 setara dengan A[i+1][0]
        //   jarak editnya adalah menghapus (i+1) chars dari s agar sama dengan t yang kosong
        v1[0] = i + 1

        // gunakan formula untuk mengisi sisa elemen di baris
        for j from 0 to n-1:
            // hitung biaya untuk A[i+1][j+1]
            deletionCost := v0[j + 1] + 1
            insertionCost := v1[j] + 1
            if s[i] = t[j]:
                substitutionCost := v0[j]
            else:
                substitutionCost := v0[j] + 1;

            v1[j + 1] := minimum(deletionCost, insertionCost, substitutionCost)

        // salin v1 (baris saat ini) ke v0 (baris sebelumnya) untuk iterasi selanjutnya
        // karena data di v1 tidak pernah dipakai lagi, swap tanpa copy dapat lebih efisien
        swap v0 with v1
    // setelah swap terakhir, hasil di v1 ada di v0
    return v0[n]

Variasi dua baris ini masih kurang optimal — jumlah memori yang diperlukan dapat dikurangi menjadi satu baris dan satu word of overhead (indeks), untuk caching yang lebih baik.

Variasi adaptif

Variasi pemrograman dinamis bukanlah implementasi yang ideal. Pendekatan adaptif dalam kasus terbaik dapat mengurangi jumlah memori yang dibutuhkan dan dapat mengurangi kompleksitas waktu menjadi linier (dalam panjang string terpendek). Sedangkan dalam kasus terburuk, kompleksitas waktunya tidak lebih dari kuadrat panjang string terpendek. Ide dari variasi ini adalah bahwa library function yang efisien (seperti std::mismatchdi C ) dapat digunakan untuk memeriksa awalan dan akhiran kedua string yang sama, dan hanya mengerjakan pemrograman dinamis bagian string yang berbeda.

Automata

Automata Levenshtein dapat secara efisien menentukan apakah sebuah string memiliki jarak edit lebih rendah dari suatu konstanta, yang diberikan dari string tertentu.

Perkiraan

Jarak Levenshtein antara dua string dengan panjang n dapat diperkirakan dalam faktor

$(\log n)^{O(1/\varepsilon )}$

di mana ε > 0 adalah parameter bebas yang dapat diatur, dalam kompleksitas waktu O(n^{1 + ε}).

Kompleksitas komputasi

Dapat dibuktikan bahwa jarak Levenshtein dari dua string dengan panjang n tidak dapat dihitung dalam waktu O(n^{2 - ε}), untuk setiap ε yang lebih besar dari nol kecuali hipotesis strong exponential time salah.