Złożoność wyszukiwania Lucene

Question

Jeśli piszę i algorytm, który wykonuje wyszukiwanie za pomocą Lucene, jak mogę podać złożoność obliczeniową? Wiem, że Lucene używa tf * idf scoring, ale nie wiem jak to jest zaimplementowane. Odkryłam, że TF * IDF ma następującą złożoności:

O(|D|+|T|) 

gdzie D jest zbiorem dokumentów i T zbiór wszystkich terminów.

Potrzebuję jednak kogoś, kto mógłby sprawdzić, czy to jest poprawne i wyjaśnić mi, dlaczego.

Dziękuję

Answer 1

Lucene zasadzie używa Vector Space Model (VSM) z systemem tf-idf. Tak więc, w standardowym ustawieniu mamy:

• zbiór dokumentów reprezentowane jako wektor
• Zapytanie tekst również reprezentowana jako wektor

ustalimy K dokumenty kolekcji z najwyższe wyniki w przestrzeni kosmicznej w zapytaniu q. Zazwyczaj szukamy tych najlepszych dokumentów K uporządkowanych według wyniku w porządku malejącym; na przykład wiele wyszukiwarek używa K = 10 do pobierania i rangowania kolejności pierwszej strony z dziesięciu najlepszych wyników.

Podstawowy algorytm do obliczania wyniki przestrzeni wektorowej jest:

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[] 

Gdzie

• Tablica Length trzyma długości (czynniki normalizacji) dla każdego z N dokumentów, natomiast tablicy Scores przechowuje oceny dla każdego z dokumentów.
• tf jest terminem terminu w dokumencie.
• w(t,q) to waga przesłanego zapytania dotyczącego danego terminu. Zauważ, że zapytanie traktowane jest jako bag of words, a wektor wag może być brany pod uwagę (tak jakby był to inny dokument).
• wf(d,q) jest logarytmiczna określenie wagi dla zapytania i dokument

Jak opisano tutaj: Complexity of vector dot-product, wektor kropka produkt jest O(n). Tutaj wymiar to liczba terminów w naszym słowniku: |T|, gdzie T to zbiór terminów.

więc złożoność czas tego algorytmu jest:

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

uważamy | Q | naprawiono, gdzie Q jest zbiorem słów w zapytaniu (który średni rozmiar jest niski, średnio zapytanie ma od 2 do 3 terminów) i D jest zbiorem wszystkich dokumentów.

Jednak w przypadku wyszukiwania zestawy te są ograniczone, a indeksy nie rosną bardzo często.W rezultacie wyszukiwania za pomocą VSM są bardzo szybkie (gdy T i D są duże, wyszukiwanie jest bardzo powolne i trzeba znaleźć alternatywne podejście).