Dizin Sıkıştırması
Dizin sıkıştırması, ters dizinlerin gönderi listelerini kompakt bir şekilde kodlayarak bir arama sisteminin daha az veri depolamasını ve sorguları daha hızlı yanıtlamasını sağlar.
Tanım
Dizin sıkıştırması, bir ters dizinin sözlüğüne ve gönderilerine tam sayı ve dize kodlama yöntemlerinin uygulanmasıdır; bu sayede depolama alanı azaltılırken, sorgu işleme sırasında gönderilerin hızlı bir şekilde çözülebilirliği korunur.
Kapsam
Bu konu, ters dizinleri sıkıştırma tekniklerini, özellikle belge tanımlayıcı boşluklarının ve terim frekanslarının değişken uzunluklu ve kelime hizalı tam sayı kodlarıyla kodlanmasını kapsamaktadır. Sözlük sıkıştırması, boşluk (delta) kodlaması, tekli (unary), gama ve Golomb gibi klasik kodlar, değişken bayt (variable-byte) ve PForDelta gibi bayt hizalı ve blok tabanlı şemalar ile sıkıştırma oranı ve kod çözme hızı arasındaki dengeyi ele almaktadır. Dizinin kendisinin oluşturulması ve onu tüketen sorgu değerlendirme stratejisi bu kapsamın dışındadır.
Temel sorular
- Belge tanımlayıcıları arasındaki boşlukları kodlamak, gönderileri neden etkili bir şekilde sıkıştırır?
- Hangi tam sayı kodları kullanılmaktadır ve bunlar sıkıştırma oranı ile kod çözme hızı arasında nasıl bir denge kurar?
- Terim sözlüğü nasıl sıkıştırılır?
- Sıkıştırılmış gönderiler, sorgu gecikmesini düşük tutacak kadar hızlı nasıl çözülebilir?
- Sıkıştırma, önbellek davranışı ve giriş/çıkış maliyeti ile nasıl etkileşime girer?
Anahtar kavramlar
- boşluk (delta) kodlaması
- değişken bayt (variable-byte) kodlaması
- gama ve Golomb-Rice kodları
- PForDelta ve blok tabanlı kodlar
- sözlük sıkıştırması
- sıkıştırma oranı
- kod çözme verimi
- SIMD / vektörleştirilmiş kod çözme
Temel kuramlar
- Gönderilerin boşluk kodlaması
- Bir gönderi listesindeki belge tanımlayıcıları artan sırada olduğu için, ardışık tanımlayıcılar arasındaki farkları (boşlukları) depolamak, özellikle yoğun gönderilere sahip sık kullanılan terimler için iyi sıkışan küçük sayılar üretmektedir.
- Sıkıştırma-hız dengesi
- Gama ve Golomb gibi bit hizalı kodlar sıkıştırmayı maksimize eder ancak yavaş çözülürken, değişken bayt (variable-byte) ve PForDelta gibi bayt hizalı ve blok tabanlı kodlar, çok daha hızlı, vektörleştirilebilir kod çözme için sıkıştırma oranından bir miktar ödün vermektedir; bu durum genellikle genel sorgu performansını artırmaktadır.
Klinik önem
Sıkıştırma, büyük ölçekte arama operasyonları için esastır: dizinleri küçülterek belleğe veya daha küçük depolama alanına sığmasını sağlar, giriş/çıkışı azaltır ve önbellek yerelliğini iyileştirir, böylece hem sorgu gecikmesini hem de donanım maliyetini düşürür. Üretim arama motorları ve açık kaynaklı arama kütüphanelerinin tümü sıkıştırılmış gönderilere dayanmaktadır.
Tarihçe
Metin dizinlerinin kompakt kodlaması, ters dosyalarla birlikte geliştirilmiştir; klasik bit hizalı kodlar (tekli, gama, Golomb) 1990'lardaki Managing Gigabytes çalışmasında sistemleştirilmiştir. Web ölçekli aramanın giderek daha hızlı kod çözme gerektirmesiyle, değişken bayt (variable-byte) ve PForDelta gibi bayt hizalı ve blok tabanlı şemalar ve daha sonra saniyede milyarlarca tam sayı işleyebilen vektörleştirilmiş kod çözücüler, vurguyu hıza kaydırmıştır.
Öne çıkan isimler
- Alistair Moffat
- Ian H. Witten
- Daniel Lemire
- Justin Zobel
İlgili konular
Temel eserler
- wittenmgb1999
- lemire2015
- manning2008
Sıkça sorulan sorular
- Sıkıştırılmış bir dizin, sıkıştırılmamış bir dizinden nasıl daha hızlı olabilir?
- Sıkıştırma, genellikle darboğaz olan diskten veya bellekten okunan veri miktarını azaltmaktadır. Modern tam sayı kodları, genellikle vektör talimatlarını kullanarak çok hızlı bir şekilde çözülmektedir, bu nedenle giriş/çıkışta kazanılan zaman ve daha iyi önbellek davranışı, kod çözme işini fazlasıyla telafi etmektedir.
- Ham belge tanımlayıcıları yerine neden boşluklar depolanır?
- Bir gönderi listesindeki belge tanımlayıcıları sıralı ve artan olduğu için, ardışık olanlar arasında küçük farklar bulunmaktadır. Bu küçük boşlukları, büyük mutlak tanımlayıcılar yerine depolamak, kompakt kodların çok az bit ile temsil edebileceği değerler üretmektedir.