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

para que sirve un motor de busqueda

Question

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

Por ejemplo, si buscaba 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 por 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

Como los índices invertidos están ordenados por docId, pueden fusionarse 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 típicas de documentos 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 clasificació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 primeros, 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);
}

}

Answer 2

En realidad, los motores de búsqueda fusionan estas listas de documentos. Obtienen un buen rendimiento al utilizar 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 (lo que hará 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, hay almacenamiento en caché, pero eso no está relacionado con el algoritmo de ejecución de consultas)

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

Sin embargo, trabajé en el motor de búsqueda líder de nuestro país, no en el verdadero motor 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 una gran cantidad de computación en límites de tiempo aceptables. Está todo muy optimizado, por supuesto, pero no hay magia ni milagros.