İndeksleme ve Sorgu İşleme
İndeksleme ve sorgu işleme, bir arama sisteminin büyük metin koleksiyonları üzerindeki sorguları hızlı bir şekilde yanıtlamasını sağlayan veri yapıları ve algoritmaları kapsar; bu genellikle tersine indeks (inverted index) aracılığıyla gerçekleştirilir.
Tanım
İndeksleme, terimleri onları içeren belgelere eşleyen, verimli arama (lookup) sağlayan veri yapılarının, özellikle tersine indeksin oluşturulmasıdır; sorgu işleme ise bir sorgu için eşleşen veya en iyi sıralanmış belgeleri hesaplamak üzere bu yapıları dolaşan algoritma kümesidir.
Kapsam
Bu alan, metin koleksiyonlarının nasıl aranabilir yapılara dönüştürüldüğünü ve sorguların bu yapılar üzerinde nasıl değerlendirildiğini kapsar: tersine indeksin oluşturulması, bunun arkasındaki belirteçleme (tokenization) ve terim-sözcük dağarcığı kararları, yer kazanmak ve erişimi hızlandırmak için gönderilerin (postings) sıkıştırılması, sıralı erişim (ranked retrieval) ve erken sonlandırma (early termination) dahil olmak üzere sorguların verimli bir şekilde işlenmesi ve joker karakter (wildcard), yazım denetimi ve fonetik eşleştirme gibi toleranslı erişim teknikleri. Bu, sıralamayı tanımlayan erişim modellerinden ve kaliteyi ölçen değerlendirme yöntemlerinden ayrı olarak, hızlı erişimin sistem mühendisliğini ele almaktadır.
Alt konular
Temel sorular
- Büyük, değişen bir koleksiyon için tersine indeks nasıl oluşturulur ve güncellenir?
- Sorgu değerlendirmesini yavaşlatmadan gönderi listeleri nasıl sıkıştırılabilir?
- Sorgular, özellikle milyonlarca belge üzerindeki sıralı sorgular, nasıl verimli bir şekilde değerlendirilir?
- Bir sistem, her belgeyi puanlamadan iyi sonuçları nasıl elde edebilir?
- Bir sistem, yazım yanlışlarını, joker karakterleri ve yaklaşık eşleşmeleri nasıl ele alır?
Anahtar kavramlar
- tersine indeks
- gönderi listesi
- belirteçleme ve terim sözcük dağarcığı
- indeks oluşturma (BSBI, SPIMI)
- indeks sıkıştırma
- belge-bazlı ve terim-bazlı değerlendirme
- dinamik budama ve erken sonlandırma
- toleranslı erişim
Temel kuramlar
- Tersine indeksin temel veri yapısı olarak kullanılması
- Her terimi, geçtiği belgelerin (ve konumların) bir gönderi listesine eşlemek, erişimin yalnızca sorgu terimlerini içeren belgelere dokunmasını sağlar ve bu da onu ölçeklenebilir metin araması için temel bir yapı haline getirir.
- Sıkıştırma-verimlilik değiş tokuşu
- Belge kimliği boşluklarını ve terim frekanslarını kompakt tam sayı kodlarıyla kodlamak, indeksi önemli ölçüde küçültür ve girdi/çıktıyı azaltarak ve önbellek davranışını iyileştirerek sorgu işlemeyi de hızlandırabilir.
- Verimli sıralı sorgu değerlendirmesi
- Belge-bazlı ve terim-bazlı stratejiler, dinamik budama ve erken sonlandırma teknikleriyle birleştiğinde, sistemlerin tüm koleksiyonu tam olarak puanlamadan en üst sıralardaki sonuçları döndürmesine olanak tanır.
Klinik önem
Tersine indeksler ve verimli sorgu işleme, web arama motorlarından açık kaynaklı arama platformlarına, kurumsal ve veritabanı tam metin aramasına kadar her üretim arama sisteminin motor odasıdır. Bunların verimliliği, sorgu gecikmesini, donanım maliyetini ve etkileşimli olarak aranabilecek koleksiyonların ölçeğini doğrudan belirlemektedir.
Tarihçe
Tersine dosyalar, en eski bilgi sistemlerinden bu yana metin arama için kullanılmaktadır, ancak indeks oluşturma, sıkıştırma ve verimli değerlendirmenin modern kuramı 1990'larda, özellikle Witten, Moffat ve Bell'in Managing Gigabytes çalışmasıyla pekiştirilmiştir. Zobel ve Moffat'ın 2006 tarihli araştırması, web ölçekli aramanın verimliliği en önemli hale getirmesiyle, yirmi yıllık tersine indeks araştırmasını sentezlemiştir.
Öne çıkan isimler
- Justin Zobel
- Alistair Moffat
- Ian H. Witten
- W. Bruce Croft
İlgili konular
Temel eserler
- zobel2006
- wittenmgb1999
- manning2008
Sıkça sorulan sorular
- Neden tersine indeks, belgeleri taramaya tercih edilir?
- Her sorgu için her belgeyi taramak, büyük ölçekte çok yavaştır. Tersine indeks, sistemin sorgu terimlerini içeren küçük belge kümesine doğrudan atlamasını sağlar, böylece sorgu süresi, tüm koleksiyonun boyutundan ziyade ilgili gönderi listelerine bağlı olur.
- İndeksi sıkıştırmak aramayı yavaşlatır mı?
- Genellikle tam tersidir. Daha küçük bir indeks, disk ve bellek trafiğini azaltır ve modern tam sayı kodları çok hızlı bir şekilde açılır, bu nedenle girdi/çıktıdan kazanılan zaman ve iyileştirilmiş önbellek davranışı genellikle kod çözme maliyetini aşar, bu da sıkıştırılmış indeksleri hem daha küçük hem de daha hızlı hale getirir.