El índice invertido

Descripción

La lección anterior te dejó con un problema visible: naive_scan funciona, pero cada búsqueda relee el corpus completo y no tiene ninguna estructura de la que colgar un criterio de peso mejor que "cuenta coincidencias". Esta lección construye la pieza que resuelve el primer problema — dejar de releer todo — y que además es el insumo que hace posible TF e IDF en la próxima lección: el índice invertido.

Un índice invertido es, en el fondo, un solo diccionario: cada término del vocabulario apunta a la lista de chunks donde aparece, junto con cuántas veces aparece en cada uno. Vas a construirlo con collections.Counter y un dict, ejecutarlo sobre los 57 chunks del corpus de Reservo, e inspeccionar sus postings (las listas de chunks por término) para un puñado de palabras clave. Al final de la lección vas a tener la estructura exacta sobre la que se calculan TF, IDF y BM25 en el resto del módulo.

Conexión con el módulo

Esta es la lección "de estructura de datos" del módulo: la 02 te mostró el problema, esta construye la solución a la parte de "no releer todo", y las lecciones 04-05 construyen el criterio de peso sobre esta misma estructura. El índice invertido que armas aquí no cambia de forma en el resto del módulo — lo que cambia es qué cálculo le aplicas encima.

Analogía: el índice temático, por dentro

En la lección 01 comparamos un índice de recuperación con el índice temático al final de un libro. Ahora mira cómo está construido ese índice por dentro: no es una lista de páginas con las palabras que contienen (eso sería, otra vez, escanear); es exactamente al revés — una lista de palabras, y para cada una, las páginas donde aparece. Por eso se llama invertido: invierte la relación "página → palabras que contiene" en "palabra → páginas que la contienen".

Índice NORMAL (lo que ya tenías):
  chunk_1 → {the, focus, room, equipment, includes, ...}
  chunk_2 → {the, studio, room, seats, four, ...}
  ...

Índice INVERTIDO (lo que construye esta lección):
  "focus"     → [chunk_1, ...]
  "equipment" → [chunk_1, chunk_15, chunk_37, ...]
  "room"      → [chunk_1, chunk_2, chunk_4, ...]
  ...

Con el índice invertido, responder "¿en qué chunks aparece 'equipment'?" es una sola búsqueda de diccionario — inverted["equipment"] — en vez de recorrer los 57 chunks preguntando uno por uno. Esa es la ganancia estructural; el criterio de peso (TF/IDF/BM25) viene después, calculado sobre esta misma estructura.

Ejemplo trabajado: construir e inspeccionar el índice invertido

El tokenizador es el mismo de la lección anterior — minúsculas, separar en secuencias de letras/dígitos, sin quitar palabras comunes (el motivo de no filtrarlas se explica en la lección 04):

import re
from collections import Counter, defaultdict

_TOKEN_RE = re.compile(r"[a-z0-9]+")


def tokenize(text):
    return _TOKEN_RE.findall(text.lower())


def build_inverted_index(chunks):
    """term -> lista ordenada de (chunk_id, term_freq_en_ese_chunk).
    También devuelve, por chunk: sus términos contados (Counter) y su
    longitud en tokens — ambos necesarios para TF/IDF/BM25 más adelante."""
    inverted = defaultdict(list)
    chunk_tokens = {}
    doc_len = {}
    for chunk in chunks:
        tokens = tokenize(chunk.text)
        counts = Counter(tokens)
        chunk_tokens[chunk.chunk_id] = counts
        doc_len[chunk.chunk_id] = len(tokens)
        for term, freq in counts.items():
            inverted[term].append((chunk.chunk_id, freq))
    for postings in inverted.values():
        postings.sort()  # orden determinista, por chunk_id
    return dict(inverted), chunk_tokens, doc_len

Tres estructuras salen de una sola pasada por el corpus: el índice invertido en sí (inverted), cuántas veces aparece cada término dentro de cada chunk (chunk_tokens, un Counter por chunk) y cuántos tokens tiene cada chunk en total (doc_len). Las tres son necesarias — el índice invertido para no releer todo, y las otras dos para el cálculo de relevancia que viene en las lecciones 04 y 05.

Lo corremos sobre el corpus completo:

chunks = build_corpus()
inverted, chunk_tokens, doc_len = build_inverted_index(chunks)

print("chunks indexados:", len(chunks))
print("tamaño del vocabulario:", len(inverted))
print()

for term in ["wifi", "refund", "boardroom", "discount"]:
    postings = inverted.get(term, [])
    print(f"'{term}' -> {len(postings)} chunks: {postings}")

Qué esperar:

chunks indexados: 57
tamaño del vocabulario: 509

'wifi' -> 8 chunks: [('boardroom-room-manual-002', 2), ('focus-room-manual-002', 2), ('lounge-room-manual-002', 2), ('operations-manual-raw-003', 1), ('phonebooth-room-manual-002', 2), ('studio-room-manual-002', 2), ('wifi-and-equipment-faq-000', 1), ('wifi-and-equipment-faq-003', 1)]
'refund' -> 4 chunks: [('cancellation-policy-003', 1), ('no-show-policy-001', 1), ('refund-policy-000', 1), ('refund-policy-003', 1)]
'boardroom' -> 8 chunks: [('boardroom-room-manual-000', 1), ('boardroom-room-manual-004', 1), ('lounge-room-manual-004', 1), ('operations-manual-raw-001', 1), ('operations-manual-raw-002', 1), ('phonebooth-room-manual-004', 1), ('studio-room-manual-000', 1), ('wifi-and-equipment-faq-000', 1)]
'discount' -> 9 chunks: [('boardroom-room-manual-003', 1), ('cancellation-policy-001', 1), ('focus-room-manual-003', 1), ('lounge-room-manual-003', 1), ('membership-tiers-faq-000', 1), ('membership-tiers-faq-001', 2), ('membership-tiers-faq-002', 1), ('phonebooth-room-manual-003', 1), ('studio-room-manual-003', 1)]

509 términos distintos, de 57 chunks — ese es el vocabulario completo del corpus de Reservo. Fíjate en los postings de "discount": aparece en 9 chunks distintos, y en membership-tiers-faq-001 aparece 2 veces (esa es la sección "How Much Discount Does the Pro Tier Get?" de la FAQ de membresías) mientras que en los demás aparece 1 vez cada uno. Esa diferencia de frecuencia — 2 contra 1 — es exactamente lo que la próxima lección convierte en una señal de relevancia (term frequency). Fíjate también en "boardroom": aparece en 8 chunks, pero ninguno de ellos es cancellation-policy — el documento real de política de cancelación (Módulo 1) nunca menciona la sala Boardroom por su nombre; quien sí la menciona es lounge-room-manual-004, en sus House Rules ("...unlike Focus, Phonebooth, and Boardroom"), junto con studio-room-manual-000 ("It sits between Focus and Boardroom...") y el manual de operaciones, que la nombra dos veces por su código de acceso y su limpieza. Este es el primer indicio, ejecutado, de algo que la lección 07 va a confirmar con una query completa: el vocabulario real del corpus no siempre coincide con lo que uno asumiría de la tabla de documentos.

Un caso límite útil: la palabra "a"

Compara los postings de una palabra de contenido contra una palabra de función:

print("postings de 'a':", len(inverted.get("a", [])), "chunks de", len(chunks))
print("postings de 'reimbursement':", inverted.get("reimbursement", []))

Qué esperar:

postings de 'a': 37 chunks de 57
postings de 'reimbursement': []

"a" aparece en 37 de los 57 chunks — casi dos tercios del corpus. Como término de búsqueda, casi no discrimina nada: saber que un chunk contiene "a" no te dice casi nada sobre su tema. En el otro extremo, "reimbursement" aparece en cero chunks — el índice invertido ni siquiera tiene esa clave. Guarda este segundo dato: es exactamente el término que la lección 06 usa para demostrar, ejecutado, el límite léxico de BM25.

Por qué esto es más rápido que naive_scan

naive_scan (lección 02) recorre los 57 chunks completos por cada búsqueda, sin importar cuántos términos tenga la query. Con el índice invertido, buscar los chunks candidatos para una query de N términos cuesta N búsquedas de diccionario — una por término — más recorrer solo las listas de postings de esos términos, que típicamente son mucho más chicas que el corpus completo:

naive_scan:          revisa los 57 chunks, para CUALQUIER query
con índice invertido: revisa solo len(postings["wifi"]) + len(postings["lounge"]) + ...
                       = 9 + varios, en vez de 57

Con 57 chunks la diferencia es cosmética — pero en un corpus real de miles o millones de chunks, la diferencia entre "revisar todo" y "revisar solo las listas de postings de los términos de la query" es la diferencia entre un sistema que responde en milisegundos y uno que no responde en un tiempo razonable. La estructura no cambia con el tamaño del corpus; lo que cambia es cuánto importa.

Errores comunes

1. Olvidar que el índice invertido guarda frecuencia, no solo presencia. inverted["boardroom"] no es solo la lista de chunks donde aparece — es una lista de pares (chunk_id, frecuencia). Si solo guardas presencia/ausencia, pierdes exactamente la señal que separa "una palabra mencionada de pasada" de "un chunk que trata principalmente ese tema".

2. Construir un índice invertido por documento en vez de por chunk. Esta guía indexa a nivel de chunk (57 entradas), no a nivel de documento (13 entradas) — porque lo que search va a devolver son chunks, no documentos completos. Si agregas por documento, pierdes la granularidad que hace útil citar la fuente exacta después.

3. No inicializar doc_len y chunk_tokens en la misma pasada que inverted. Las tres estructuras se calculan sobre el mismo tokenizado de cada chunk — calcularlas por separado significa tokenizar cada chunk más de una vez, y arriesgarse a que un cambio en el tokenizador quede aplicado en una estructura y no en otra.

4. Asumir que un vocabulario de 509 términos es "poco" y no importa optimizar. Con este corpus de juguete, cualquier enfoque funciona rápido. El punto de esta lección no es la velocidad en 57 chunks — es la estructura correcta, la misma que un sistema con millones de chunks necesita sin cambiar de forma.

5. Pensar que el índice invertido, por sí solo, ya es un criterio de relevancia. No lo es — es la estructura que hace posible calcular relevancia rápido. inverted["boardroom"] te dice en qué 6 chunks aparece la palabra, pero no te dice todavía cuál de esos 6 es el más relevante para una query completa — ni te dice si esos 6 son realmente sobre Boardroom, o solo la mencionan de pasada. Eso es TF/IDF/BM25, lecciones 04 y 05.

Ejercicios

Ejercicio 1: Inspecciona los postings de "cancel" vs "cancellation" (Fácil)

Sin ejecutar nada primero, predice: ¿"cancel" y "cancellation" van a compartir los mismos postings en el índice invertido, o son entradas distintas? Luego ejecuta el índice y confirma.

chunks = build_corpus()
inverted, chunk_tokens, doc_len = build_inverted_index(chunks)

print("cancel:", inverted.get("cancel", []))
print("cancellation:", inverted.get("cancellation", []))

cancel: [('cancellation-policy-000', 1)]
cancellation: [('cancellation-policy-002', 1), ('cancellation-policy-003', 1), ('membership-tiers-faq-000', 2), ('membership-tiers-faq-002', 1), ('no-show-policy-000', 2), ('no-show-policy-001', 1), ('payment-methods-faq-000', 1), ('refund-policy-000', 1), ('refund-policy-001', 1), ('refund-policy-002', 1), ('refund-policy-003', 1)]

Ejercicio 2: Construye el índice sobre un subconjunto (Medio)

Construye el índice invertido usando solo los chunks de doc_id "focus-room-manual", "studio-room-manual" y "boardroom-room-manual" (los tres manuales de sala más chicos). Reporta el tamaño del vocabulario resultante y los postings de la palabra "room".

chunks = build_corpus()
subset = [c for c in chunks if c.doc_id in
          {"focus-room-manual", "studio-room-manual", "boardroom-room-manual"}]
print("chunks en el subconjunto:", len(subset))

inverted, chunk_tokens, doc_len = build_inverted_index(subset)
print("vocabulario del subconjunto:", len(inverted))
print("postings de 'room':", inverted.get("room", []))

chunks en el subconjunto: 15
vocabulario del subconjunto: 179
postings de 'room': [('boardroom-room-manual-000', 2), ('boardroom-room-manual-001', 1), ('boardroom-room-manual-004', 1), ('focus-room-manual-000', 2), ('focus-room-manual-001', 1), ('focus-room-manual-004', 1), ('studio-room-manual-000', 1), ('studio-room-manual-001', 1)]

Ejercicio 3: Encuentra el término más frecuente del corpus (Difícil)

Sin usar ninguna librería fuera de stdlib, escribe código que recorra el índice invertido completo del corpus de Reservo y encuentre: (a) el término que aparece en más chunks distintos (mayor len(postings)), y (b) el par (chunk_id, término) con la mayor frecuencia dentro de un solo chunk. Ejecuta y reporta ambos.

chunks = build_corpus()
inverted, chunk_tokens, doc_len = build_inverted_index(chunks)

# (a) término en más chunks distintos
most_common_term = max(inverted.items(), key=lambda pair: len(pair[1]))
print(f"término en más chunks: '{most_common_term[0]}' en {len(most_common_term[1])} chunks")

# (b) mayor frecuencia dentro de un solo chunk
best = None
for term, postings in inverted.items():
    for chunk_id, freq in postings:
        if best is None or freq > best[2]:
            best = (chunk_id, term, freq)
print(f"mayor frecuencia en un solo chunk: {best[1]!r} aparece {best[2]} veces en {best[0]}")

término en más chunks: 'the' en 50 chunks
mayor frecuencia en un solo chunk: 'a' aparece 6 veces en refund-policy-000

Resumen y siguiente paso

• El índice invertido es un diccionario término → lista de (chunk_id, frecuencia) — la estructura que evita releer el corpus completo en cada búsqueda.
• Lo construimos con collections.Counter y defaultdict, en una sola pasada por los 57 chunks del corpus de Reservo: 509 términos de vocabulario, con postings que van desde "reimbursement" (0 chunks) hasta "the" (50 chunks).
• El índice se calcula a nivel de chunk, no de documento — porque search va a devolver chunks con su cita exacta, no documentos completos.
• El índice invertido resuelve el problema de "no releer todo"; no resuelve todavía el problema de peso (¿cuál de los chunks que contienen un término es el más relevante?) — eso es exactamente lo que arman TF e IDF en la próxima lección, calculados sobre esta misma estructura.

Siguiente lección: 04 — Term frequency e IDF. Convertimos las listas de postings en un criterio de relevancia real: cuánto se repite un término dentro de un chunk, y qué tan raro es en todo el corpus — a mano, y verificado con una matriz numpy.

Recursos adicionales

1. Python — collections.defaultdict — La estructura que simplifica construir el índice invertido sin chequear manualmente si una clave ya existe.
2. Python — collections.Counter — El conteo de términos por chunk que alimenta tanto el índice invertido como TF/BM25.
3. Manning, Raghavan & Schütze — Introduction to Information Retrieval, cap. 1: "Boolean retrieval" — La referencia académica estándar de la estructura de índice invertido que esta lección implementa.
4. Python 3.14 — What's New — La versión con la que se ejecuta todo el código de este módulo.