Bagaimana cara kerja inverted index?

Question

IT Interview Practice · Accepted Answer

**Inverted index memetakan sebuah istilah ke dokumen yang memuatnya.** Dengan cara ini, mesin pencari dapat menemukan kandidat dokumen tanpa membaca semua dokumen dari awal sampai akhir untuk setiap pencarian.

Bayangkan indeks pada bagian belakang buku: cari sebuah kata, lalu buka halaman yang tercantum. Dalam mesin pencari, pengenal dokumen menggantikan nomor halaman.

## 1. Mulai dari koleksi kecil

Misalnya kita memiliki tiga dokumen dan menggunakan analyzer sederhana yang mengubah teks menjadi huruf kecil lalu memisahkan kata. Analyzer adalah rangkaian langkah yang mengubah teks menjadi istilah yang dapat dicari.

```text
D1: Red apple
D2: Green apple
D3: Red car

apple -> D1, D2
car   -> D3
green -> D2
red   -> D1, D3
```

Arah semula adalah dokumen menuju kata. Indeks membalik arah tersebut menjadi kata menuju dokumen, sesuai namanya. Daftar dokumen yang cocok untuk setiap istilah disebut posting list.

## 2. Gunakan daftar untuk menjawab kueri

Untuk kueri yang mensyaratkan red sekaligus apple, baca kedua posting list dan ambil irisannya: D1 terdapat dalam keduanya. Untuk kueri yang menerima salah satu istilah, ambil gabungannya: D1, D2, dan D3 menjadi kandidat.

Contoh ini menjelaskan pencocokan, bukan peringkat. Jika beberapa dokumen cocok, mesin dapat memberi skor menggunakan informasi seperti frekuensi istilah dan seberapa umum istilah tersebut dalam koleksi. Menemukan kecocokan dan menentukan urutannya merupakan langkah yang berkaitan tetapi terpisah.

## 3. Selaraskan pengindeksan dan pencarian

Kueri harus dianalisis dengan cara yang kompatibel dengan istilah dalam indeks. Jika pengindeksan mengubah Red menjadi red tetapi pencarian mencari istilah literal Red, kecocokan yang diinginkan dapat terlewat.

Analisis yang tepat bergantung pada field. Deskripsi produk mendapat manfaat dari analisis teks; pengenal pesanan yang persis biasanya membutuhkan pencocokan tepat. Memecah pengenal menjadi kata biasa dapat mengubah maknanya. Lihat penjelasan Elastic mengenai [pencarian teks lengkap](https://www.elastic.co/docs/solutions/search/full-text/how-full-text-works).

## 4. Simpan informasi yang cukup untuk pertanyaan yang diajukan

Dokumen yang memuat red dan apple belum tentu memuat frasa red apple. Untuk menjawab kueri frasa, indeks membutuhkan posisi kata agar mesin dapat memeriksa urutan dan kedekatannya.

- Pengenal dokumen menjawab dokumen mana yang memuat istilah.
- Frekuensi membantu menjelaskan seberapa sering istilah muncul.
- Posisi mendukung pertanyaan tentang letak istilah relatif terhadap istilah lain.

Menyimpan lebih banyak informasi memungkinkan kueri yang lebih kaya, tetapi meningkatkan ukuran indeks dan pekerjaan pengindeksan. Indeks yang berguna ditentukan oleh pencarian yang harus didukung aplikasi.

## 5. Pahami biaya menjaga indeks tetap mutakhir

Ketika teks sumber berubah, indeks pencariannya juga harus diperbarui. Sistem seperti Elasticsearch mengelola data terindeks dalam segmen dan menggabungkannya seiring waktu; pembaruan tidak berarti semua posting list yang ada langsung ditulis ulang di tempat. Keterlihatan dalam pencarian juga bergantung pada perilaku refresh mesin.

Karena itu, perhitungkan penyimpanan tambahan, biaya pengindeksan, dan kemungkinan jeda antara penulisan dokumen dan kemunculannya dalam pencarian. Inverted index sangat berguna untuk pencarian teks berbasis istilah; indeks ini bukan pengganti universal bagi indeks untuk pencarian tepat, rentang, atau akses transaksional.

1. Mulai dari koleksi kecil

2. Gunakan daftar untuk menjawab kueri

3. Selaraskan pengindeksan dan pencarian

4. Simpan informasi yang cukup untuk pertanyaan yang diajukan

5. Pahami biaya menjaga indeks tetap mutakhir

Pertanyaan terkait