Lunes, tocho. Cuando buscas una palabra en un millón de documentos, no se lee ninguno: se consulta un índice invertido, que es el índice del final de un libro, pero para todo el corpus.
Tres documentos de juguete:
1: el gato come pescado
2: el perro come carne
3: el gato duerme
El índice invertido asocia cada término con la lista (ordenada) de documentos donde aparece, su posting list:
el -> [1, 2, 3]
gato -> [1, 3]
come -> [1, 2]
pescado -> [1]
perro -> [2]
carne -> [2]
duerme -> [3]
La consulta gato AND come es una intersección de dos listas ordenadas, que se hace con dos punteros en tiempo lineal:
def interseccion(a, b):
i = j = 0
salida = []
while i < len(a) and j < len(b):
if a[i] == b[j]:
salida.append(a[i]); i += 1; j += 1
elif a[i] < b[j]:
i += 1
else:
j += 1
return salida
print(interseccion([1, 3], [1, 2])) # [1]
Lo que hace que esto funcione a gran escala:
- Listas ordenadas por identificador, para poder intersectar sin ordenar al vuelo.
- Compresión por deltas: en vez de
[1000, 1003, 1010]se guarda[1000, 3, 7], que son números pequeños y se codifican con pocos bytes (códigos de longitud variable). - Saltos (skip pointers): para intersectar una lista corta con una larguísima, se salta en la grande en vez de recorrerla entera.
- Segmentos inmutables: el índice se construye en bloques que nunca se modifican, y se fusionan en segundo plano. Es la misma idea que un LSM-tree: escribir secuencial, fusionar luego.
- Si además guardas las posiciones de cada palabra, puedes buscar frases exactas.
Después de encontrar los candidatos viene el orden: ahí entra un ranking como BM25 (da para otro tocho), pero el ranking solo se aplica a lo que el índice ya ha filtrado.