Membangun inverted index dengan database relasional

Dalam program untuk melakukan pencarian, salah satu metode agar pencarian bisa dilakukan dengan efisien adalah dengan melakukan pengindeksan (indexing). Dengan mengindeks dokumen yang akan dicari, maka pencarian dokumen dengan query tertentu tidak perlu dilakukan secara sekuensial atau diperiksa satu-persatu.

Inverted index adalah indeks yang terbentuk dari proses pengindeksan. Secara umum strukturnya sebagai berikut:

Dapat dilihat tabel sebelah kiri adalah “dokumen” atau teks yang akan diindeks. Sedangkan sebelah kanan adalah hasil pengindeksan. Jadi term (sederhananya: kata) yang ada pada dokumen menunjuk ke ID dokumen yang mengandung term tersebut.

Secara intuitif, indeks seperti ini mirip dengan indeks pada buku. Pada buku yang cukup tebal sering dijumpai halaman “Indeks” yang cara kerjanya sama dengan inverted index seperti ini. Lebih lengkap mengenai inverted index silakan baca buku Introduction to Information Retrieval.

Untuk membangun indeks seperti ini dengan database relasional (misalnya MySQL), perlu dibuat tabel yang merepresentasikan struktur indeks ini. Pada posting sebelumnya saya membuat struktur tabel indeks, namun rasanya itu kurang efisien, sehingga struktur tabel indeks harus diubah. Tabel “index” yang lama hanya menjadi tabel sementara dalam proses pengindeksan. Sedangkan tabel indeks yang sebenarnya diubah menjadi berikut, beserta contoh isinya:

Jadi daftar dokumen yang mengandung term tertentu disimpan sebagai string dalam kolom posting_list, begitu pula frekuensi term pada dokumen (freq_list).

Untuk membentuk indeks seperti itu dalam database, saya membaginya menjadi dua fase sebagai berikut:

Fase I (pembangunan indeks sementara)

1. Baca seluruh teks dari dokumen
2. Untuk setiap dokumen yang dibaca:
   1. Lakukan tokenisasi atau ekstraksi term dari teks dokumen
   2. Hitung frekuensi setiap term dalam dokumen
   3. Untuk setiap term yang didapat, masukkan ke tabel indeks sementara (term, ID dokumen, frekuensi term)
3. Selesai, indeks sementara terbentuk

Fase II (pembangunan indeks)

1. Baca seluruh term unik dari tabel indeks sementara
2. Untuk setiap term:
   1. Baca daftar ID dokumen yang mengandung term tersebut (dari tabel indeks sementara)
   2. Selain ID, baca frekuensi term dalam dokumen dan jumlah dokumen yang mengandung term
   3. Gabungkan daftar ID dokumen dengan koma, inilah posting_list
   4. Gabungkan daftar frekuensi term dengan koma, inilah freq_list
   5. Masukkan dalam tabel indeks yang sesungguhnya (term, jumlah dokumen, ID dokumen, frekuensi term)
3. Selesai, indeks terbentuk
4. Hapus tabel indeks sementara

Dengan langkah-langkah di atas, maka akan terbentuk inverted index seperti ilustrasi yang dibuat. Implementasi saya dengan PHP dan term berupa trigram dapat dilihat pada repositori kode.

Mengenai cara pencarian dengan struktur indeks seperti ini, Insya Allah akan dibahas kemudian.