Jarak Levenshtein

Metode ini banyak digunakan dalam bidang ilmu komputer, khususnya pada sistem pemeriksa ejaan, mesin pencari, pengolahan bahasa alami, dan berbagai aplikasi yang perlu membandingkan teks. Semakin kecil nilai jarak Levenshtein, semakin mirip kedua string tersebut.

Untuk menghitungnya, saya membuat sebuah matriks yang setiap selnya menyimpan biaya minimum untuk mengubah satu substring menjadi substring lainnya. Dengan mengisi matriks secara bertahap, saya dapat menentukan jumlah operasi penyuntingan paling sedikit yang diperlukan.

Berbeda dengan jarak Hamming, jarak Levenshtein dapat digunakan untuk membandingkan string yang panjangnya berbeda.

Contoh Praktis

Misalkan terdapat dua string berikut:

$$ s = "kitten" $$

$$ t = "sitting" $$

Tujuannya adalah mencari jumlah minimum operasi yang diperlukan untuk mengubah kata kitten menjadi sitting.

1. Penggantian karakter
   Ganti huruf \( k \) dengan \( s \): $$ "kitten" \rightarrow "sitten" $$
2. Penggantian karakter
   Ganti huruf \( e \) dengan \( i \): $$ "sitten" \rightarrow "sittin" $$
3. Penyisipan karakter
   Tambahkan huruf \( g \) di akhir kata: $$ "sittin" \rightarrow "sitting" $$

Dalam contoh ini diperlukan total 3 operasi, yaitu dua kali penggantian karakter dan satu kali penyisipan karakter. Dengan demikian, jarak Levenshtein antara kitten dan sitting adalah:

$$ d(\text{kitten},\text{sitting}) = 3 $$

Proses perhitungan biasanya direpresentasikan menggunakan sebuah matriks berukuran \( (m+1) \times (n+1) \), dengan:

• \( m \) = panjang string kitten = 6
• \( n \) = panjang string sitting = 7

Baris dan kolom tambahan digunakan untuk merepresentasikan string kosong, sehingga transformasi dari atau menuju string kosong dapat dihitung dengan mudah.

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

Sel \( (0, j) \) menunjukkan biaya untuk mengubah string kosong menjadi substring dari "sitting" hingga posisi \( j \). Karena setiap karakter harus ditambahkan satu per satu, nilainya meningkat secara bertahap dari 0 hingga 7.

Sebaliknya, sel \( (i, 0) \) menunjukkan biaya untuk mengubah substring dari "kitten" hingga posisi \( i \) menjadi string kosong. Dalam kasus ini, setiap karakter harus dihapus, sehingga nilainya meningkat dari 0 hingga 6.

Untuk menghitung nilai pada setiap sel \( (i, j) \), saya membandingkan tiga kemungkinan operasi:

1. Menghapus satu karakter dari "kitten", yaitu nilai sel di atas ditambah \( 1 \)
2. Menyisipkan satu karakter ke dalam "kitten", yaitu nilai sel di sebelah kiri ditambah \( 1 \)
3. Mengganti satu karakter, yaitu nilai sel diagonal ditambah \( 1 \) jika kedua karakter berbeda. Jika kedua karakter sama, tidak ada biaya tambahan.

Dengan aturan tersebut, matriks dapat diisi secara bertahap hingga seluruh nilai diketahui:

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

Perhatikan bahwa untuk mengubah string kosong menjadi "s", "si", "sit", dan seterusnya, biaya bertambah satu pada setiap kolom karena diperlukan satu penyisipan tambahan.

Hal yang sama berlaku pada kolom pertama. Untuk mengubah "k", "ki", "kit", dan seterusnya menjadi string kosong, diperlukan satu penghapusan tambahan pada setiap baris.

• Sel (1,1) menunjukkan biaya untuk mengubah "k" menjadi "s". Nilainya adalah 1 karena cukup dilakukan satu substitusi (k→s).
  
• Sel (2,2) menunjukkan biaya untuk mengubah "ki" menjadi "si". Nilainya tetap 1 karena karakter kedua pada kedua string sama, yaitu \( i \).
• Sel (3,3) menunjukkan biaya untuk mengubah "kit" menjadi "sit". Nilainya masih 1 karena karakter ketiga sama, yaitu \( t \).
• Sel (4,4) menunjukkan biaya untuk mengubah "kitt" menjadi "sitt". Nilainya tetap 1 karena karakter keempat juga sama, yaitu \( t \).
• Sel (5,5) menunjukkan biaya untuk mengubah "kitte" menjadi "sitti". Nilainya menjadi 2 karena diperlukan satu substitusi tambahan, yaitu \( e \rightarrow i \).
  
• Sel (6,6) menunjukkan biaya untuk mengubah "kitten" menjadi "sittin". Nilainya tetap 2 karena karakter terakhir yang dibandingkan sama, yaitu \( n \).
• Sel (6,7) menunjukkan biaya untuk mengubah "kitten" menjadi "sitting". Nilainya menjadi 3 karena diperlukan satu penyisipan tambahan, yaitu huruf \( g \).
  

Setelah seluruh matriks terisi, nilai pada sel terakhir memberikan hasil akhir perhitungan.

Sel kanan bawah \( (6,7) \) berisi biaya minimum untuk mengubah "kitten" menjadi "sitting", yaitu 3.

Nilai tersebut merupakan jarak Levenshtein antara kedua string. Dalam contoh ini, transformasi dapat dilakukan melalui dua substitusi (`k → s` dan `e → i`) serta satu penyisipan (`g`).

Topologi yang Diinduksi oleh Jarak Levenshtein

Jarak Levenshtein tidak hanya berguna dalam pengolahan teks, tetapi juga memiliki makna matematis yang lebih mendalam. Karena memenuhi seluruh aksioma metrik, jarak ini dapat digunakan untuk membangun sebuah ruang metrik pada himpunan string.

1. Non-negativitas
   Untuk setiap pasangan string \( x \) dan \( y \), berlaku \( D_L(x,y) \ge 0 \). Selain itu, \( D_L(x,y)=0 \) jika dan hanya jika \( x=y \). Dengan kata lain, sebuah string memiliki jarak nol hanya terhadap dirinya sendiri.
2. Simetri
   Jarak Levenshtein bersifat simetris: $$ D_L(x,y)=D_L(y,x) $$ Jumlah operasi minimum untuk mengubah \( x \) menjadi \( y \) sama dengan jumlah operasi minimum untuk mengubah \( y \) menjadi \( x \).
3. Ketaksamaan Segitiga
   Untuk setiap string \( x \), \( y \), dan \( z \), berlaku: $$ D_L(x,z) \le D_L(x,y)+D_L(y,z) $$ Artinya, jarak langsung dari \( x \) ke \( z \) tidak pernah lebih besar daripada jarak yang diperoleh jika transformasi dilakukan melalui string perantara \( y \).

Karena memenuhi ketiga sifat tersebut, jarak Levenshtein membentuk sebuah ruang metrik pada himpunan string.

Dari ruang metrik ini, kita dapat mendefinisikan sebuah topologi metrik terinduksi.

Untuk sebuah string \( x \) dan radius \( r \), bola terbuka yang berpusat di \( x \) didefinisikan sebagai:

$$ B(x,r)=\{y \mid D_L(x,y)

Artinya, himpunan tersebut memuat semua string yang jaraknya dari \( x \) lebih kecil daripada \( r \).

Seluruh himpunan terbuka dalam topologi ini dapat diperoleh dari gabungan bola-bola terbuka semacam itu.

Konsep ini memiliki banyak aplikasi praktis. Dalam sistem koreksi ejaan otomatis, misalnya, kata yang memiliki jarak Levenshtein kecil terhadap kata dalam kamus sering dianggap sebagai kandidat koreksi yang baik.

Dengan demikian, string dapat diperlakukan sebagai titik-titik dalam sebuah ruang metrik, sehingga hubungan kedekatan antarstring dapat dianalisis menggunakan alat-alat topologi.

Contoh Praktis

Misalkan:

$$ X=\{\text{"cat"},\text{"bat"},\text{"cut"}\} $$

Untuk setiap elemen dalam \( X \), saya membentuk bola terbuka dengan radius \( r=2 \):

$$ B(x,r)=\{y \mid D_L(x,y)

Karena jarak Levenshtein selalu berupa bilangan bulat, kondisi \( D_L(x,y)<2 \) berarti string tersebut berjarak 0 atau 1 dari pusatnya.

Catatan: bola terbuka dengan radius 2 tidak mencakup titik-titik yang berjarak tepat 2 dari pusat karena syaratnya adalah "kurang dari 2". Jika ingin memasukkan batas tersebut, digunakan bola tertutup: $$ \overline{B}(x,2)=\{y \mid D_L(x,y)\le 2\} $$

Sekarang perhatikan setiap bola terbuka:

1. Bola terbuka berpusat di "cat" $$ B(\text{"cat"},2)=\{\text{"cat"},\text{"bat"},\text{"cut"}\} $$ String "bat" dan "cut" masing-masing berjarak 1 dari "cat", sehingga keduanya termasuk dalam bola terbuka ini.
2. Bola terbuka berpusat di "bat" $$ B(\text{"bat"},2)=\{\text{"bat"},\text{"cat"}\} $$ Hanya "cat" yang berada pada jarak kurang dari 2 dari "bat" di dalam himpunan \( X \).
3. Bola terbuka berpusat di "cut" $$ B(\text{"cut"},2)=\{\text{"cut"},\text{"cat"}\} $$ String "cat" dapat diperoleh dari "cut" dengan satu substitusi karakter, sehingga termasuk dalam bola terbuka ini.

Himpunan-himpunan tersebut dapat digunakan sebagai elemen basis untuk topologi yang diinduksi oleh jarak Levenshtein pada \( X \).

Dari basis ini, seluruh himpunan terbuka lainnya dapat diperoleh melalui operasi gabungan.

Sebagai contoh:

$$ B(\text{"bat"},2)\cup B(\text{"cut"},2) $$

Karena:

$$ B(\text{"bat"},2)=\{\text{"bat"},\text{"cat"}\} $$

dan

$$ B(\text{"cut"},2)=\{\text{"cut"},\text{"cat"}\} $$

maka:

$$ B(\text{"bat"},2)\cup B(\text{"cut"},2)=\{\text{"cat"},\text{"bat"},\text{"cut"}\} $$

Himpunan \( \{\text{"cat"},\text{"bat"},\text{"cut"}\} \) merupakan salah satu himpunan terbuka dalam topologi tersebut.

Dengan cara ini, topologi metrik yang diinduksi oleh jarak Levenshtein memungkinkan kita membangun dan menganalisis struktur kedekatan pada himpunan string secara formal.

Dan seterusnya.