Indeks Terbalik

Indeks terbalik memetakan setiap istilah dalam suatu koleksi ke daftar posting dokumen yang mengandungnya, memungkinkan sistem pencarian untuk menemukan dokumen yang cocok tanpa memindai setiap dokumen.

Definition

Indeks terbalik adalah struktur data yang terdiri dari kamus istilah terindeks, yang masing-masing menunjuk ke daftar posting yang menghitung dokumen yang mengandung istilah tersebut, seringkali dianotasi dengan frekuensi dan posisi istilah, sehingga pengambilan dapat dilakukan dengan menginterseksi atau menggabungkan daftar posting.

Scope

Topik ini mencakup struktur dan konstruksi indeks terbalik: kamus istilah, daftar posting yang merekam pengidentifikasi dokumen, frekuensi istilah, dan posisi, serta algoritma yang membangun dan memperbarui indeks pada koleksi besar, termasuk pengindeksan berbasis pengurutan blok (blocked sort-based indexing) dan pengindeksan dalam memori satu-lintasan (single-pass in-memory indexing). Ini membahas informasi posisi untuk kueri frasa dan rekayasa pemeliharaan indeks, sementara kompresi dan strategi evaluasi kueri diserahkan ke topik terkait.

Core questions

• Apa yang terkandung dalam entri kamus dan daftar postingnya?
• Bagaimana posisi disimpan untuk mendukung kueri frasa dan kedekatan?
• Bagaimana indeks terbalik dibangun ketika koleksi terlalu besar untuk memori?
• Bagaimana indeks diperbarui saat dokumen ditambahkan, diubah, atau dihapus?
• Bagaimana daftar posting mendukung interseksi yang efisien untuk kueri konjungtif?

Key concepts

• kamus istilah
• daftar posting
• pengidentifikasi dokumen
• indeks posisi
• penyimpanan frekuensi istilah
• pengindeksan berbasis pengurutan blok (BSBI)
• pengindeksan dalam memori satu-lintasan (SPIMI)
• penggabungan dan pembaruan indeks

Key theories

Organisasi kamus dan posting

Memisahkan kamus istilah yang ringkas dari daftar posting dengan panjang variabel memungkinkan sistem mencari istilah dengan cepat dan kemudian hanya mengalirkan dokumen yang relevan, yang merupakan dasar struktural dari semua pengambilan indeks terbalik.

Konstruksi indeks yang skalabel

Metode berbasis disk seperti pengindeksan berbasis pengurutan blok dan pengindeksan dalam memori satu-lintasan membangun berkas terbalik untuk koleksi yang jauh lebih besar dari memori dengan mengakumulasi dan menggabungkan indeks parsial.

Clinical relevance

Indeks terbalik adalah struktur data sentral dari hampir semua sistem pencarian teks, termasuk mesin pencari web, platform pencarian sumber terbuka seperti Lucene dan turunannya, serta pencarian teks lengkap basis data. Desainnya mengatur jenis kueri apa yang didukung dan seberapa cepat serta murah kueri tersebut dapat dijawab.

History

Berkas terbalik digunakan dalam sistem pengambilan bibliografi awal dan menjadi struktur standar untuk pencarian teks lengkap seiring pertumbuhan koleksi. Penelitian pada tahun 1990-an dan 2000-an, termasuk metode konstruksi yang skalabel seperti pengindeksan dalam memori satu-lintasan, membuatnya praktis untuk mengindeks korpora berskala web, dan struktur ini sekarang menjadi dasar pustaka pencarian sumber terbuka yang banyak digunakan.

Key figures

• Justin Zobel
• Alistair Moffat
• Steffen Heinz

Seminal works

• zobel2006
• heinz2003
• manning2008

Frequently asked questions

Mengapa disebut indeks 'terbalik'?

Indeks normal (maju) mencantumkan, untuk setiap dokumen, istilah-istilah yang dikandungnya. Indeks terbalik membalikkan pemetaan ini untuk mencantumkan, untuk setiap istilah, dokumen-dokumen yang mengandungnya. Pembalikan inilah yang membuat pencarian berbasis istilah menjadi cepat.

Untuk apa indeks posisi digunakan?

Indeks posisi menyimpan posisi di mana setiap istilah muncul dalam setiap dokumen. Ini memungkinkan sistem menjawab kueri frasa dan kueri kedekatan, di mana urutan atau kedekatan istilah penting, bukan hanya apakah istilah tersebut muncul di suatu tempat dalam dokumen.