Bangun inverted index

Pertanyaan

Bagaimana mencari kata di jutaan dokumen tanpa membaca semuanya satu per satu?

Setelah baca ini, kamu bisa membangun inverted index kecil dengan tangan, menjawab query AND, OR, dan NOT dari posting list, dan menjelaskan pilihan normalisasi yang mengubah hasil pencarian.

Prasyarat dan contoh

Kamu sudah paham indeks basis data (M04) dan kenapa data besar dipartisi (M07). Pembahasan di sini belum butuh pengetahuan soal ranking.

Sebuah toko resep punya 2 juta dokumen. Pengguna mengetik "ayam goreng". Cara paling polos: WHERE body LIKE '%ayam%' AND body LIKE '%goreng%'. Itu membaca semua 2 juta baris, dan indeks B-tree biasa nggak membantu karena pola diawali wildcard. Kalau satu dokumen rata-rata 2 KB, sekali query membaca sekitar 4 GB.

Inverted index membalik arah pandang. Alih-alih "dokumen punya kata apa", simpan "kata ini ada di dokumen mana". Query jadi pencarian kata di kamus kecil, bukan pemindaian seluruh isi.

Mekanisme

1. Tokenisasi. Pecah teks jadi token, lalu normalisasi. Ambil empat dokumen:

| id | isi | | --- | ------------------------- | | 1 | Sate ayam Madura enak | | 2 | Nasi goreng ayam pedas | | 3 | Sate kambing dan nasi | | 4 | Ayam goreng |

Setelah huruf kecil dan pemisahan di spasi, tiap token dicatat bersama id dokumennya.

2. Posting list. Untuk tiap term, simpan daftar id dokumen yang terurut naik.

ayam    -> [1, 2, 4]
goreng  -> [2, 4]
nasi    -> [2, 3]
sate    -> [1, 3]
pedas   -> [2]
kambing -> [3]
madura  -> [1]
enak    -> [1]
dan     -> [3]

Kumpulan term dengan pointer ke posting list-nya disebut kamus (dictionary). Kamus biasanya disimpan terurut supaya mencari term itu binary search, bukan pemindaian.

3. Query Boolean sebagai operasi himpunan. Karena kedua daftar terurut, penggabungan cukup satu kali jalan dengan dua pointer, biayanya O(m + n).

• ayam AND goreng: irisan [1,2,4] dan [2,4] menghasilkan [2,4].
• sate OR nasi: gabungan [1,3] dan [2,3] menghasilkan [1,2,3].
• ayam AND NOT goreng: [1,2,4] dikurangi [2,4] menghasilkan [1].

Urutkan term dari yang daftarnya paling pendek. Untuk ayam AND pedas AND goreng, mulai dari pedas (1 dokumen) lalu cek yang lain hanya pada kandidat itu.

4. Posisi token. Kalau kamu ingin mendukung frasa "ayam goreng" (kata berurutan), tiap posting menyimpan juga posisi token di dokumen: ayam -> {2: [3], 4: [1]}. Biayanya nyata: indeks dengan posisi biasanya jauh lebih besar daripada indeks tanpa posisi.

5. Normalisasi. Setiap pilihan menukar recall dengan presisi.

• Huruf kecil dan Unicode. Hampir selalu aman. Samakan bentuk karakter (NFKC) supaya "ｉｎｄｅｘ" lebar penuh cocok dengan "index".
• Stopword (dan, yang, di). Indeks lebih kecil, tapi frasa seperti "yang pertama" ikut kehilangan arti. Kini banyak mesin tetap menyimpan stopword dan mengandalkan ranking.
• Stemming (memasak menjadi masak). Recall naik karena bentuk kata disatukan, tapi stemmer yang agresif juga menyatukan kata yang artinya berbeda sehingga presisi turun.

6. Ukuran. Untuk 10 juta dokumen dengan rata-rata 300 token, ada sekitar 3 miliar posting. Dengan delta encoding (simpan selisih id) dan varint, satu posting sering cukup 1 sampai 2 byte, jadi kira-kira 3 sampai 6 GB tanpa posisi. Itu muat di satu mesin, dan jauh lebih kecil dari korpus aslinya.

Saat rancangan ini gagal

• Analyzer berbeda antara indeks dan query. Hasil kosong tanpa pesan salah. Simpan nama dan versi analyzer bersama indeks, dan uji dengan dokumen contoh.
• Mengubah analyzer tanpa membangun ulang. Dokumen lama diindeks dengan aturan lama, dokumen baru dengan aturan baru, dan pencarian jadi nggak konsisten. Perubahan analyzer berarti reindex penuh.
• Posting list super panjang. Term seperti "dan" ada di hampir semua dokumen, dan menggabungkannya itu mahal. Tanpa stopword, mesin harus pintar melewati bagian daftar yang nggak relevan.
• Teks tanpa spasi. Bahasa seperti Jepang dan Thai nggak bisa dipisah dengan spasi dan butuh tokenizer khusus. Untuk bahasa Indonesia, masalah yang lebih sering muncul adalah kata gabungan, singkatan, dan ejaan campuran.

Contoh tandingan: korpus 5.000 catatan internal dengan beberapa query per menit. LIKE atau full-text bawaan basis data sudah cukup, dan inverted index terpisah cuma menambah sistem yang harus dioperasikan dan disinkronkan.

Latihan

Bangun inverted index (tanpa posisi) dari empat dokumen ini, huruf kecil saja, tanpa stemming:

1. "Soto ayam Lamongan"
2. "Soto betawi dan nasi"
3. "Nasi ayam Hainan"
4. "Ayam bakar Taliwang"

Lalu jawab: ayam AND nasi, soto OR bakar, dan ayam AND NOT soto.

ayam     -> [1, 3, 4]
soto     -> [1, 2]
lamongan -> [1]
betawi   -> [2]
dan      -> [2]
nasi     -> [2, 3]
hainan   -> [3]
bakar    -> [4]
taliwang -> [4]

Terkait

• Lanjut ke M11.02 Urutkan hasil teks: setelah dapat kandidat, mana yang tampil duluan?
• Kamus term yang terurut mirip struktur indeks di M04, tapi nilai yang disimpan adalah daftar id.
• Lab L11 dan proyek B08 membangun mesin pencarian kecil dari bahan ini. Keduanya belum tersedia.

Catatan

• Asumsi: dokumen berbahasa Indonesia dengan tokenisasi spasi, dan korpus muat di satu mesin.
• Yang nggak dibahas: format segmen di disk, kompresi lanjutan (skip list, Roaring bitmap), dan stemmer bahasa Indonesia tertentu.
• Angka ukuran indeks adalah perkiraan orde besar, bukan hasil pengukuran pada satu mesin.
• Terakhir ditinjau: 26 Oktober 2026.