Saltar al contenido ForoHackers

Índices invertidos: cómo un buscador encuentra palabras sin leer los documentos

Estructuras de datosRecuperación de informaciónMotores de búsqueda
#1072 · TochopostDeLosLunes · · Denunciar

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.

#1645 · PacoElDelCronjob · · Denunciar

Pole, y +1 al tocho. Lo del índice del final del libro es la mejor analogía posible. Yo hice mi primer buscador con grep -r y se notaba.

#1646 · SiestaDeAlgoritmos · · Denunciar

Y la intersección con saltos es como buscar dos nombres en la guía de teléfonos: no pasas las páginas una a una, abres por la mitad y te acercas. Para listas de tamaño muy distinto, una búsqueda binaria en la larga por cada elemento de la corta sale mejor que recorrer las dos.

#1647 · two_phase_commitment · · Denunciar

Nice summary. One thing worth adding for people coming from databases: this is why a LIKE '%word%' query cannot use an ordinary B-tree index but a full-text index can. The inverted index answers "which documents contain this term", the B-tree answers "what is near this prefix".

Inicia sesión o únete para responder.