Buscar sin leer todos los textos
Un índice invertido es una tabla que guarda, para cada palabra, la lista de los documentos donde aparece. Con ella, un buscador responde en un instante sin leer los textos uno por uno.
Imagina el tablón de avisos de una facultad con un millón de papeles. Si buscas «beca» y tienes que leerlos todos, tardas horas. Si alguien te da una lista con los papeles que dicen «beca», tardas un segundo.
Al final de esta lección
Nota
Puedo encontrar los documentos de una palabra con un índice invertido.
Palabras clave
| Palabra | Qué significa |
|---|---|
| Documento | cada texto que se puede buscar, con su número |
| Índice invertido | una tabla de palabra a lista de documentos |
| Lista de apariciones | los números de los documentos de una palabra |
| Consulta | las palabras que escribe quien busca |
| Búsqueda booleana | una consulta que combina palabras con Y, O y NO |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Leer todos los textos no escala
La forma más simple de buscar es recorrer cada documento y mirar si contiene la palabra. Funciona con seis textos y es un desastre con un millón.
Cada consulta nueva obliga a leer todo otra vez. El trabajo crece con el número de documentos, aunque la palabra solo esté en tres.
Ejemplo resuelto: seis avisos de la facultad
| Número | Texto del aviso |
|---|---|
| 1 | la biblioteca abre a las ocho |
| 2 | el bus a la facultad sale a las ocho |
| 3 | la beca de comedor tiene plazo en marzo |
| 4 | la biblioteca cierra tarde en marzo |
| 5 | bicicletas gratis en la facultad |
| 6 | plazo de pago en la facultad en marzo |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
El índice invertido va de palabra a documento
Un texto normal va del documento a sus palabras. El índice invertido hace lo contrario: va de cada palabra a los documentos que la contienen. Por eso se llama «invertido».
Cada palabra tiene su lista de apariciones, con los números de los documentos en orden. Se construye una sola vez, antes de que nadie busque.
El índice de los seis avisos
| Palabra | Lista de apariciones |
|---|---|
| biblioteca | 1, 4 |
| facultad | 2, 5, 6 |
| marzo | 3, 4, 6 |
| plazo | 3, 6 |
| bus | 2 |
| la | 1, 2, 3, 4, 5, 6 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Construye un índice invertido
# Un índice invertido: cada palabra apunta a los avisos donde sale.
avisos = {
1: "la biblioteca abre a las ocho",
2: "el bus a la facultad sale a las ocho",
3: "la beca de comedor tiene plazo en marzo",
4: "la biblioteca cierra tarde en marzo",
5: "bicicletas gratis en la facultad",
6: "plazo de pago en la facultad en marzo",
}
indice = {}
for numero in avisos:
for palabra in avisos[numero].split():
if palabra not in indice:
indice[palabra] = []
if numero not in indice[palabra]:
indice[palabra].append(numero)
print(indice["marzo"])
print(indice["facultad"])
# Cambia "marzo" por "biblioteca" y ejecuta.
Consulta las listas de tres palabras
docker exec jupyter python3 -c "d={1:'la biblioteca abre a las ocho',2:'el bus a la facultad sale a las ocho',3:'la beca de comedor tiene plazo en marzo',4:'la biblioteca cierra tarde en marzo',5:'bicicletas gratis en la facultad',6:'plazo de pago en la facultad en marzo'}; i={}; [i.setdefault(w,[]).append(n) for n in d for w in set(d[n].split())]; print(i['marzo'], i['facultad'], i['plazo'])"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Y, O y NO combinan las listas
Una búsqueda booleana combina palabras con tres operaciones. Y deja los documentos que están en las dos listas. O deja los que están en al menos una. NO quita los de una lista.
El índice hace esto sin leer ningún texto: solo compara listas de números cortas.
Ejemplo resuelto: cuatro consultas
| Consulta | Qué se hace con las listas | Resultado |
|---|---|---|
| marzo Y facultad | Los números comunes de 3, 4, 6 y 2, 5, 6 | 6 |
| biblioteca O plazo | Todos los de 1, 4 y de 3, 6 | 1, 3, 4, 6 |
| marzo NO plazo | De 3, 4, 6 quitar 3, 6 | 4 |
| bus Y marzo | Los comunes de 2 y de 3, 4, 6 | ninguno |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Cruza dos listas con Y
# Y: los avisos que están en las dos listas.
marzo = [3, 4, 6]
facultad = [2, 5, 6]
los_dos = []
for numero in marzo:
if numero in facultad:
los_dos.append(numero)
print(los_dos)
# Cambia facultad por [3, 6] y mira qué sale.
Un error muy común
Advertencia
Mucha gente cree que el índice se hace de nuevo en cada búsqueda. No es así: se construye una vez y se reutiliza en todas las consultas. Solo hay que actualizarlo cuando entra un documento nuevo.
Para ir más lejos: tu propio tablón
Escribe ocho avisos cortos sobre tu vida de estudiante, con números del 1 al 8. Construye su índice con el código de arriba.
Busca tres consultas con Y y dos con O. Antes de ejecutar, escribe a mano qué documentos esperas.