Bir Lucene araştırmasının karmaşıklığı

Question

Lucene kullanarak arama yapan bir yazım ve algoritma yazarsam, bunun hesaplama karmaşıklığını nasıl belirleyebilirim? Lucene'nin tf * idf puanlamasını kullandığını biliyorum ama nasıl uygulandığını bilmiyorum. Ben tf * idf aşağıdaki karmaşıklığı sahip olduğunu tespit ettik: D belge ve T tüm terimlerin kümesi setidir

O(|D|+|T|) 

. Bununla birlikte, bunun doğru olup olmadığını kontrol edip nedenini açıklayan birisine ihtiyacım var.

Eğer

Answer 1

Lucene temelde tf-idf şeması ile Vector Space Model (VSM) kullanan ederiz. Yani, standart ortamda elimizdeki:

• belgelerin bir koleksiyonu bir vektör
• da bir vektör olarak temsil Bir metin sorgusu

Biz koleksiyonunun K belgeleri ile tespit olarak temsil her q sorgusundaki en yüksek vektör alanı puanları. Tipik olarak, bu K üst belgelerini azalan düzende sırayla sıraya koyarız; Örneğin, çoğu arama motoru, en iyi on sonucun ilk sayfasını almak ve sıralamak için K = 10 kullanır.

vektör uzayı puanları hesaplamak için temel algoritmasıdır:

• dizi LengthN belgelerin her biri için uzunlukları (normalleştirme faktörleri) tutan

  float Scores[N] = 0 
  Initialize Length[N] 
  for each query term t 
  do calculate w(t,q) and fetch postings list for t (stored in the index) 
      for each pair d,tf(t,d) in postings list 
      do Scores[d] += wf(t,d) X w(t,q) (dot product) 
  Read the array Length[d] 
  for each d 
  do Scored[d] = Scores[d]/Length[d] 
  return Top K components of Scores[] 
  

  , dizi Scores oysa Her bir belge için puanları tutar.

• tf belgede bir terimin sıklığı terimidir. Belirli bir terim için gönderilen sorgunun ağırlığı
• w(t,q)'dur. Sorgunun bag of words olarak kabul edildiğini ve ağırlıklar vektörünün dikkate alınabileceğini unutmayın (başka bir belge gibi). Complexity of vector dot-product, vektör nokta ürün O(n) geçerli:
• wf(d,q) sorgu ve belgeye burada anlatıldığı gibi

için logaritmik terim ağırlıklandırma olduğunu. Burada boyut, kelime haznemizdeki terimlerin sayısıdır: |T|, burada T terimler kümesidir.

Yani, bu algoritmanın zaman karmaşıklığı: biz düşünün

O(|Q|· |D| · |T|) = O(|D| · |T|) 

| Q | Sabit, burada Q sorgudaki sözcüklerin kümesidir (ortalama boyut düşüktür, ortalamada bir sorgu 2 ve 3 terimler içerir) ve D tüm belgelerin kümesidir. Bununla birlikte, bir arama için bu kümeler sınırlıdır ve dizinler çok sık büyümeye eğilimlidir.Sonuç olarak, VSM kullanarak yapılan aramalar gerçekten hızlıdır (T ve D büyük olduğunda arama gerçekten yavaştır ve alternatif bir yaklaşım bulmak zorundadır).