Algoritma Fuzzy Bitap

Algoritma Fuzzy Bitap adalah salah satu algoritma yang dapat digunakan untuk mencari dimana sebuah string (dalam kasus ini dinamakan sebagai pola) apakah ditemukan di dalam kumpulan string lain dengan ukuran yang lebih besar. Contoh yang dibahas kali ini adalah mengenai pencarian kata dari sebuah input teks.
Bitap akan memberitahu apakah data input memliki pola yang “kira-kira sama dengan” pola yang sedang dicari, dimana perkiraan ditentukan dengan menggunakan Levenshtein Distance. Algoritma dimulai dengan melakukan perhitungan bitmask yang mengandung 1 bit untuk setiap elemen dalam pola, kemudian pencarian akan dilakukan dengan cara operasi bitwise, dimana pencarian tersebut sangat cepat dilakukan.
Untuk melakukan pencarian Bitap menggunakan Fuzzy, maka diperlukan ekstensi bit array R menjadi beberapa dimensi. Jika sebelumnya hanya digunakan sebuah array R yang berubah seiring dengan panjang teks, maka sekarang bit array R memiliki beberapa dimensi untuk menampung perwakilan prefiks dari pola yang cocok dengan suffiks dari string yang sedang dihitung dengan error yang paling minimal. Dalam hal ini error ditentukan dari penyisipan/penghapusan/penggantian karakter, yang dapat dilakukan pada saat menghitung Levenshtein Distance.

Langkah-langkah penggunaan algoritma ini adalah

1. Tentukan teks yang digunakan sebagai input
Diasumsikan data input adalah sebagai berikut:
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

2. Tentukan pola kata kunci yang digunakan dalam pencarian
Diasumsikan pola adalah sebagai berikut
labor

3. Lakukan pencarian kata kunci menggunakan algoritma ini

Dim idxKata As Integer = CariPola(input, pola)

* Gunakan fungsi ini untuk mencari pola pada data input

Public Function CariPola(input As String, pola As String, k As Integer) As Integer
	Dim hasil As Integer = -1
	Dim m As Integer = pola.Length
	Dim R As Integer()
	Dim maskPola As Integer() = New Integer(127) {}
	Dim i As Integer, d As Integer

	If String.IsNullOrEmpty(pola) Then
		Return 0
	End If
	If m > 31 Then
		Return -1 'Error: Pola terlalu panjang
	End If

	R = New Integer((k + 1) * 4 - 1) {}
	For i = 0 To k
		R(i) = Not 1
	Next

	For i = 0 To 127
		maskPola(i) = Not 0
	Next

	For i = 0 To m - 1
		maskPola(Convert.ToInt32(pola(i))) = maskPola(Convert.ToInt32(pola(i))) And Not (1 << i)
	Next

	For i = 0 To input.Length - 1
		Dim oldRd1 As Integer = R(0)

		R(0) = R(0) Or maskPola(Convert.ToInt32(input(i)))
		R(0) <<= 1

		For d = 1 To k
			Dim tmp As Integer = R(d)

			R(d) = (oldRd1 And (R(d) Or maskPola(Convert.ToInt32(input(i))))) << 1
			oldRd1 = tmp
		Next

		If 0 = (R(k) And (1 << m)) Then
			hasil = (i - m) + 1
			Exit For
		End If
	Next

	Return hasil
End Function

Hasil akhir adalah: (klik untuk perbesar gambar)

Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:

Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.