Kompresi Indeks

Kompresi indeks mengodekan daftar posting dari indeks terbalik secara ringkas sehingga sistem pencarian menyimpan lebih sedikit data dan menjawab kueri lebih cepat.

Definition

Kompresi indeks adalah penerapan metode pengodean bilangan bulat dan string pada kamus dan posting dari indeks terbalik untuk mengurangi jejak penyimpanannya sambil menjaga posting dapat didekode dengan cepat selama pemrosesan kueri.

Scope

Topik ini mencakup teknik untuk mengompresi indeks terbalik, terutama pengodean celah pengidentifikasi dokumen dan frekuensi istilah dengan kode bilangan bulat panjang variabel dan sejajar kata. Ini membahas kompresi kamus, pengodean celah (delta), kode klasik seperti unary, gamma, dan Golomb-Rice, skema sejajar byte dan berbasis blok seperti variable-byte dan PForDelta, serta pertukaran antara rasio kompresi dan kecepatan dekode. Ini tidak termasuk konstruksi indeks itu sendiri dan strategi evaluasi kueri yang menggunakannya.

Core questions

• Mengapa pengodean celah antara pengidentifikasi dokumen mengompresi posting secara efektif?
• Kode bilangan bulat apa yang digunakan, dan bagaimana mereka menukar rasio kompresi dengan kecepatan dekode?
• Bagaimana kamus istilah itu sendiri dikompresi?
• Bagaimana posting terkompresi dapat didekode cukup cepat untuk menjaga latensi kueri tetap rendah?
• Bagaimana kompresi berinteraksi dengan perilaku cache dan biaya input/output?

Key concepts

• pengodean celah (delta)
• pengodean variable-byte
• kode gamma dan Golomb-Rice
• PForDelta dan kode berbasis blok
• kompresi kamus
• rasio kompresi
• throughput dekode
• dekode SIMD / tervektorisasi

Key theories

Pengodean celah posting

Karena pengidentifikasi dokumen dalam daftar posting meningkat, menyimpan perbedaan (celah) antara pengidentifikasi berurutan menghasilkan angka kecil yang dapat dikompresi dengan baik, terutama untuk istilah yang sering muncul dengan posting padat.

Pertukaran kompresi-kecepatan

Kode sejajar bit seperti gamma dan Golomb memaksimalkan kompresi tetapi mendekode secara perlahan, sedangkan kode sejajar byte dan berbasis blok seperti variable-byte dan PForDelta mengorbankan beberapa rasio untuk dekode yang jauh lebih cepat dan dapat diverktorisasi, yang seringkali memenangkan kinerja kueri secara keseluruhan.

Clinical relevance

Kompresi sangat penting untuk mengoperasikan pencarian dalam skala besar: ini mengecilkan indeks sehingga muat dalam memori atau penyimpanan yang lebih kecil, mengurangi input/output dan meningkatkan lokalitas cache, dan dengan demikian menurunkan latensi kueri dan biaya perangkat keras. Mesin pencari produksi dan pustaka pencarian sumber terbuka semuanya mengandalkan posting terkompresi.

History

Pengodean ringkas indeks teks dikembangkan bersamaan dengan berkas terbalik, dengan kode sejajar bit klasik (unary, gamma, Golomb) disistematisasi dalam karya Managing Gigabytes pada tahun 1990-an. Karena pencarian skala web menuntut dekode yang semakin cepat, skema sejajar byte dan berbasis blok seperti variable-byte dan PForDelta, dan kemudian dekoder tervektorisasi yang mampu memproses miliaran bilangan bulat per detik, menggeser penekanan ke arah kecepatan.

Key figures

• Alistair Moffat
• Ian H. Witten
• Daniel Lemire
• Justin Zobel

Seminal works

• wittenmgb1999
• lemire2015
• manning2008

Frequently asked questions

Bagaimana indeks terkompresi bisa lebih cepat daripada yang tidak terkompresi?

Kompresi mengurangi jumlah data yang dibaca dari disk atau memori, yang seringkali menjadi hambatan. Kode bilangan bulat modern mendekode dengan sangat cepat, seringkali menggunakan instruksi vektor, sehingga waktu yang dihemat pada input/output dan perilaku cache yang lebih baik lebih dari mengkompensasi pekerjaan dekode.

Mengapa menyimpan celah daripada pengidentifikasi dokumen mentah?

Pengidentifikasi dokumen dalam daftar posting diurutkan dan meningkat, sehingga yang berurutan berbeda dengan jumlah kecil. Menyimpan celah kecil tersebut daripada pengidentifikasi absolut yang besar menghasilkan nilai yang dapat direpresentasikan oleh kode ringkas dalam sangat sedikit bit.