Ters İndeksler
Ters bir indeks, bir koleksiyondaki her terimi, onu içeren belgelerin bir gönderi listesiyle eşleyerek, bir arama sisteminin her belgeyi taramadan eşleşen belgeleri bulmasını sağlamaktadır.
Tanım
Ters bir indeks, indekslenmiş terimlerin bir sözlüğünden oluşan bir veri yapısıdır; her terim, terimi içeren belgeleri listeleyen, genellikle frekanslar ve terim konumları ile açıklanan bir gönderi listesine işaret etmektedir, böylece geri çağırma, gönderi listelerini kesiştirerek veya birleştirerek gerçekleştirilebilmektedir.
Kapsam
Bu konu, ters indeksin yapısını ve oluşturulmasını kapsamaktadır: terim sözlüğü, belge tanımlayıcılarını, terim frekanslarını ve konumlarını kaydeden gönderi listeleri ve bloklu sıralama tabanlı indeksleme (blocked sort-based indexing) ile tek geçişli bellek içi indeksleme (single-pass in-memory indexing) dahil olmak üzere büyük koleksiyonlar üzerinde indeksleri oluşturan ve güncelleyen algoritmalar. İfade sorguları için konumsal bilgileri ve indeks bakımının mühendisliğini ele almakta, sıkıştırma ve sorgu değerlendirme stratejisini ise bitişik konulara bırakmaktadır.
Temel sorular
- Bir sözlük girişi ve gönderi listesi ne içermektedir?
- İfade ve yakınlık sorgularını desteklemek için konumlar nasıl depolanmaktadır?
- Koleksiyon bellek için çok büyük olduğunda ters indeks nasıl oluşturulmaktadır?
- Belgeler eklendikçe, değiştirildikçe veya silindikçe bir indeks nasıl güncellenmektedir?
- Gönderi listeleri, birleşimsel sorgular için verimli kesişimi nasıl desteklemektedir?
Anahtar kavramlar
- terim sözlüğü
- gönderi listesi
- belge tanımlayıcıları
- konumsal indeks
- terim frekansı depolama
- bloklu sıralama tabanlı indeksleme (BSBI)
- tek geçişli bellek içi indeksleme (SPIMI)
- indeks birleştirme ve güncellemeler
Temel kuramlar
- Sözlük ve gönderi organizasyonu
- Kompakt bir terim sözlüğünü değişken uzunluktaki gönderi listelerinden ayırmak, sistemin bir terimi hızlıca aramasını ve ardından yalnızca ilgili belgeleri akışla iletmesini sağlamaktadır; ki bu, tüm ters indeks geri çağırmanın yapısal temelini oluşturmaktadır.
- Ölçeklenebilir indeks oluşturma
- Bloklu sıralama tabanlı indeksleme (blocked sort-based indexing) ve tek geçişli bellek içi indeksleme (single-pass in-memory indexing) gibi disk tabanlı yöntemler, kısmi indeksleri biriktirerek ve birleştirerek bellekten çok daha büyük koleksiyonlar için ters dosyalar oluşturmaktadır.
Klinik önem
Ters indeks, web arama motorları, Lucene ve türevleri gibi açık kaynaklı arama platformları ve veritabanı tam metin araması dahil olmak üzere neredeyse tüm metin arama sistemlerinin merkezi veri yapısıdır. Tasarımı, hangi sorgu türlerinin desteklendiğini ve bunların ne kadar hızlı ve uygun maliyetle yanıtlanabileceğini belirlemektedir.
Tarihçe
Ters dosyalar, erken dönem bibliyografik geri çağırma sistemlerinde kullanılmış ve koleksiyonlar büyüdükçe tam metin araması için standart yapı haline gelmiştir. 1990'lı ve 2000'li yıllardaki araştırmalar, tek geçişli bellek içi indeksleme (single-pass in-memory indexing) gibi ölçeklenebilir oluşturma yöntemleri dahil olmak üzere, web ölçeğindeki korpusları indekslemeyi pratik hale getirmiş ve bu yapı günümüzde yaygın olarak kullanılan açık kaynaklı arama kütüphanelerinin temelini oluşturmaktadır.
Öne çıkan isimler
- Justin Zobel
- Alistair Moffat
- Steffen Heinz
İlgili konular
Temel eserler
- zobel2006
- heinz2003
- manning2008
Sıkça sorulan sorular
- Neden 'ters' indeks olarak adlandırılmaktadır?
- Normal (ileri) bir indeks, her belge için içerdiği terimleri listelemektedir. Ters indeks, bu eşlemeyi tersine çevirerek, her terim için onu içeren belgeleri listelemektedir. Bu tersine çevirme, terim tabanlı aramayı hızlı kılan şeydir.
- Konumsal indeks ne için kullanılmaktadır?
- Konumsal bir indeks, her terimin her belge içinde geçtiği konumları depolamaktadır. Bu, sistemin terimlerin yalnızca belgede bir yerde görünüp görünmediğine değil, terimlerin sırasının veya yakınlığının önemli olduğu ifade sorgularını ve yakınlık sorgularını yanıtlamasını sağlamaktadır.