Fuzzy Search Algorithm adalah teknik pencarian data yang mampu menemukan kecocokan string atau teks meskipun kueri yang dimasukkan oleh pengguna mengalami kesalahan ketik (typo), perbedaan ejaan, atau tidak sama persis dengan data di dalam basis data. Algoritma ini sangat krusial dalam sistem pencarian modern seperti e-commerce, mesin pencari, dan autocomplete.
Berbeda dengan pencarian eksak (exact match) seperti operator SQL WHERE kolom = 'nilai' yang bernilai biner (cocok atau tidak), fuzzy search menggunakan ukuran kemiripan berbasis probabilitas atau jarak edit (edit distance). Sistem akan menghitung berapa banyak modifikasi (penghapusan, penambahan, atau penggantian karakter) yang diperlukan untuk mengubah satu kata menjadi kata lainnya.
Metode Utama dalam Fuzzy Search
Ada beberapa pendekatan matematis dan algoritmik yang sering digunakan untuk mengimplementasikan pencarian fuzzy dalam sistem perangkat lunak:
| Nama Algoritma | Fokus Utama | Kelebihan | Kekurangan |
|---|---|---|---|
| Levenshtein Distance | Menghitung jumlah operasi minimum (sisip, hapus, ganti) | Akurat untuk kesalahan ketik pendek | Lambat untuk dataset teks yang sangat besar |
| Jaro-Winkler | Mengukur jarak kecocokan karakter dan transposisi | Sangat baik untuk pencarian nama orang | Kurang optimal untuk teks panjang |
| N-Gram / Trigram | Memecah string menjadi potongan karakter kecil (n-gram) | Cepat dan efisien untuk pencarian parsial | Membutuhkan ruang penyimpanan indeks tambahan |
| Soundex | Pengindeksan berdasarkan kemiripan pelafalan fonetik | Bagus untuk kata yang terdengar mirip | Terbatas pada bahasa tertentu (umumnya Inggris) |
Implementasi Levenshtein Distance dengan Python
Berikut adalah contoh implementasi dasar menggunakan bahasa pemrograman Python untuk menghitung jarak Levenshtein antara dua string tanpa pustaka eksternal:
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]
# Contoh Penggunaan
print(levenshtein_distance("algoritma", "algoritme")) # Output: 1
Penerapan Fuzzy Search di Lingkungan Produksi
Untuk skala industri dan data yang masif, mengandalkan perhitungan manual seperti fungsi di atas akan membebani CPU. Oleh karena itu, pengembang umumnya menggunakan mesin pencari (search engine) yang sudah mendayagunakan indeks terbalik (inverted index) dan algoritma fuzzy secara native:
- Elasticsearch / OpenSearch: Menyediakan fitur
fuzzy querydengan parameterfuzziness(AUTO, 0, 1, 2) berdasarkan Levenshtein Edit Distance. - PostgreSQL: Mendukung ekstensi
pg_trgm(Trigram) untuk pencarian similarity teks secara efisien langsung di dalam database relasional. - Algolia / Typesense: Mesin pencari instan berbasis cloud yang mengotomatiskan koreksi typo secara real-time.
Tips Optimasi Performa
Pencarian fuzzy membutuhkan sumber daya komputasi yang lebih tinggi dibanding pencarian eksak. Batasi ambang batas (threshold) kemiripan agar sistem tidak mengembalikan hasil yang terlalu jauh dari relevansi kueri. Gunakan indeks berbasis trigram atau n-gram pada kolom database yang sering menjadi target pencarian teks untuk menjaga latensi tetap rendah di bawah 50 milidetik.