¿Cómo combinan los motores de búsqueda los resultados de un índice invertido?

Question

¿Cómo combinan los motores de búsqueda los resultados de un índice invertido?

Por ejemplo, si busqué los índices invertidos de las palabras "perro" y "murciélago", habría dos listas enormes de cada documento que contuviera una de las dos palabras.

Dudo que un motor de búsqueda recorra estas listas, documento a documento, e intente encontrar coincidencias con los resultados de las listas. ¿Qué se hace algorítmicamente para hacer que este proceso de fusión sea extremadamente rápido?

Answer 1

En realidad, los motores de búsqueda hacen fusionan estas listas de documentos. Obtienen un buen rendimiento utilizando otras técnicas, la más importante de las cuales es la poda: por ejemplo, para cada palabra, los documentos se almacenan en orden de reducción del pagerank, y para obtener resultados que tienen la posibilidad de entrar en los primeros 10 (que se le mostrará al usuario) puede atravesar una porción bastante pequeña de las listas de perros y murciélagos, por ejemplo, los primeros mil. (Y, por supuesto, no hay almacenamiento en caché, pero que no está relacionado con el algoritmo de ejecución de la consulta muy)

Además, después de todo, no hay que muchos documentos sobre perros y sobre los murciélagos: incluso si se trata de millones, resulta en fracciones de segundo con una buena implementación.

---

P.S. Sin embargo, trabajé en el motor de búsqueda líder de nuestro país, no en el motor mismo de nuestro producto de búsqueda principal, pero hablé con sus desarrolladores y me sorprendió saber que los algoritmos de ejecución de consultas son bastante tontos: resulta que uno puede aplastar un enorme cantidad de cómputo en límites de tiempo aceptables. Está todo muy optimizado, por supuesto, pero no hay magia ni milagros.

Answer 2

Dado que los índices invertidos están ordenados por docId, se pueden combinar muy rápido. [si una de las palabras comienza en docId 23 y la segunda en docId 100001, puede avanzar de inmediato a docId 100001 o superior también en la primera lista. ]

Dado que las intersecciones de documentos típicos son casi pocos millones, se pueden ordenar por rango muy rápido. Busqué 'perro gato' [palabras muy comunes de 2 palabras] que arrojó solo 54 millones de visitas.

La ordenación de enteros aleatorios de 10 millones tomó solo 2.3 segundos en mi Mac con código de subproceso único [1 millón tardó 206 ms!] Y como normalmente tenemos que seleccionar solo los 10 principales, ni siquiera se requiere la clasificación completa.

Aquí está el código si alguien quiere probar la velocidad de ordenación y demasiado perezoso para escribir código.

import java.lang.*; 
import java.math.*; 
import java.util.*; 

public class SortTest { 
    public static void main(String[] args) { 
    int count = Integer.parseInt(args[0]); 

Random random = new Random(); 
int[] values = new int[count]; 
int[] bogusValues = new int[100000]; //screw cache 
    for(int i = 0; i < values.length;++i) { 
    values[i] = random.nextInt(count); 
} 
for(int i = 0; i < bogusValues.length;++i) { 
    bogusValues[i] = random.nextInt(count); 
} 
long start = System.currentTimeMillis(); 
System.out.println(start); 
     Arrays.sort(values); 
System.out.println(System.currentTimeMillis()); 
System.out.println(System.currentTimeMillis()-start); 
    Arrays.sort(bogusValues); 
} 

}