Complejidad de la búsqueda de un Lucene

Question

Si escribo un algoritmo que realiza una búsqueda usando Lucene, ¿cómo puedo indicar la complejidad computacional del mismo? Sé que Lucene usa la puntuación de tf * idf, pero no sé cómo se implementa. He encontrado que la TF * IDF tiene la siguiente complejidad:

O(|D|+|T|) 

donde D es el conjunto de documentos y T el conjunto de todos los términos.

Sin embargo, necesito a alguien que pueda verificar si esto es correcto y explicarme por qué.

Gracias

Answer 1

Lucene básicamente utiliza un Vector Space Model (VSM) con un esquema de tf-idf. Así, en el establecimiento de normas que tenemos:

• Una colección de documentos de cada uno representado como un vector
• Una consulta de texto también representado como un vector

se determina la K documentos de la colección con los puntajes de espacio vectorial más altos en la consulta q. Por lo general, buscamos estos K documentos principales ordenados por puntaje en orden decreciente; por ejemplo, muchos motores de búsqueda usan K = 10 para recuperar y clasificar la primera página de los diez mejores resultados.

El algoritmo básico para el cálculo de puntuaciones de espacio vectorial es:

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

Dónde

• La matriz Length sostiene las longitudes (factores de normalización) para cada uno de los N documentos, mientras que la matriz Scores contiene los puntajes de cada uno de los documentos.
• tf es el término frecuencia de un término en un documento.
• w(t,q) es el peso de la consulta enviada para un término determinado. Tenga en cuenta que la consulta se trata como bag of words y se puede considerar el vector de ponderaciones (como si fuera otro documento).
• wf(d,q) es la ponderación logarítmica plazo para la consulta y el documento

Como se describe aquí: Complexity of vector dot-product, vector de puntos subproducto es O(n). Aquí la dimensión es el número de términos en nuestro vocabulario: |T|, donde T es el conjunto de términos.

Así, la complejidad del tiempo de este algoritmo es:

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

consideramos | Q | fijo, donde Q es el conjunto de palabras de la consulta (cuyo tamaño promedio es bajo, en promedio una consulta tiene entre 2 y 3 términos) y D es el conjunto de todos los documentos.

Sin embargo, para una búsqueda, estos conjuntos son acotados y los índices no suelen crecer con mucha frecuencia.Por lo tanto, como resultado, las búsquedas que utilizan VSM son realmente rápidas (cuando T y D son grandes, la búsqueda es realmente lenta y hay que buscar un enfoque alternativo).