Definisi dan Konsep Jarak Levenshtein
Jarak Levenshtein adalah metrik matematis yang digunakan untuk mengukur perbedaan antara dua string atau barisan simbol. Dalam komputasi, algoritma ini menghitung jumlah minimum operasi penyuntingan—yaitu penyisipan (insertion), penghapusan (deletion), atau penggantian (substitution)—yang diperlukan untuk mengubah satu string menjadi string lainnya.
Algoritma ini merupakan fondasi utama dalam pencarian string samar (fuzzy string searching), koreksi ejaan, dan analisis bioinformatika untuk membandingkan urutan DNA.
Tabel Perbandingan Metrik Kemiripan
| Metrik | Fokus Utama | Kegunaan Umum |
|---|---|---|
| Jarak Levenshtein | Jumlah operasi edit | Koreksi ejaan, fuzzy search |
| Jarak Hamming | Perbedaan posisi karakter | String dengan panjang yang sama |
| Jarak Damerau-Levenshtein | Edit + Transposisi | Deteksi typo pengetikan |
| Kemiripan Kosinus | Orientasi vektor | Analisis teks dokumen |
Implementasi Algoritma dalam Kode
Berikut adalah implementasi standar menggunakan pendekatan pemrograman dinamis (dynamic programming) untuk efisiensi komputasi:
def levenshtein_distance(s1, s2):
if len(s1) < len(s2):
return levenshtein_distance(s2, s1)
if len(s2) == 0:
return len(s1)
previous_row = range(len(s2) + 1)
for i, c1 in enumerate(s1):
current_row = [i + 1]
for j, c2 in enumerate(s2):
insertions = previous_row[j + 1] + 1
deletions = current_row[j] + 1
substitutions = previous_row[j] + (c1 != c2)
current_row.append(min(insertions, deletions, substitutions))
previous_row = current_row
return previous_row[-1]Langkah-Langkah Teknis
- Inisialisasi matriks atau baris untuk menyimpan hasil perhitungan sub-masalah.
- Iterasi melalui setiap karakter dari kedua string yang dibandingkan.
- Hitung biaya untuk setiap operasi (tambah, hapus, ganti).
- Ambil nilai minimum dari ketiga operasi tersebut untuk setiap sel.
- Hasil akhir berada pada sel terakhir matriks yang merepresentasikan total jarak edit.
Tips Troubleshooting
Saat mengimplementasikan algoritma ini pada dataset besar, perhatikan kompleksitas waktu O(n*m). Jika performa menjadi kendala, pertimbangkan untuk menggunakan teknik early exit atau membatasi ambang batas (threshold) jarak maksimum yang diizinkan agar proses pencarian tidak memakan sumber daya CPU secara berlebihan.