Aula 24 - Arquivos Invertidos (Índices Invertidos)
Motivação: como os buscadores encontram documentos?
| Cenário: você tem 10 milhões de páginas web e um usuário pesquisa por "gato". Como encontrar, entre todas elas, as que contêm essa palavra? |
Opção 1: busca sequencial
Ler as páginas uma a uma e procurar a palavra em cada uma. Se cada página tem cerca de 1.000 palavras:
10.000.000 páginas × 1.000 palavras = 10 bilhões de palavras lidas a cada consulta (cerca de 10 segundos, supondo 109 leituras por segundo).
Opção 2: pré-processar e usar um índice invertido
Antes de qualquer consulta, lemos as páginas uma única vez e montamos uma estrutura que, para cada palavra, guarda a lista dos documentos que a contêm. Na hora da consulta, basta procurar "gato" nessa estrutura e ler a lista. Se "gato" aparece em 1.000 páginas:
~1.000 leituras (um lookup, isto é, a procura da palavra "gato" na estrutura, que devolve direto a sua lista, + a leitura da lista com 1.000 documentos), cerca de 10 milhões de vezes menos trabalho.
| Busca sequencial | Índice invertido | |
|---|---|---|
| Quando se trabalha | a cada consulta | uma vez, antes das consultas |
| Trabalho por consulta | 10 bilhões de palavras | ~1.000 docIDs |
| Depende do tamanho da coleção? | sim, linearmente | quase não: depende de quantos documentos contêm a palavra |
Recuperação de Informação (RI)
Esse problema pertence à Recuperação de Informação: como encontrar, numa coleção enorme de documentos, os que são relevantes para uma consulta. Ela envolve indexar (organizar a coleção para buscar rápido, o assunto desta aula), ranquear (ordenar os resultados) e avaliar a qualidade deles. No início (anos 1960-70), servia a sistemas locais, como catálogos de bibliotecas; nos anos 1990, com a web, surgiram os buscadores (como o Google, em 1998), com coleções de milhões e depois bilhões de páginas; hoje a mesma ideia alimenta também os assistentes baseados em LLMs (veja a curiosidade sobre RAG abaixo).
Onde isso é usado?
|
Exemplos: Google e outros mecanismos de busca; PostgreSQL (índice GIN, Generalized Inverted Index, para busca em texto); busca em documentos jurídicos e acadêmicos; busca de símbolos e referências em editores de código. Curiosidade — RAG: em Retrieval-Augmented Generation, um modelo de linguagem (LLM) primeiro busca documentos relevantes e só depois gera a resposta com base neles. Essa busca pode usar índices invertidos, índices vetoriais (embeddings) ou os dois combinados. |
1. O que é um índice invertido?
Você já usa um índice invertido: o índice remissivo no final dos livros didáticos. Para saber onde um livro fala de "fila", ninguém lê o livro inteiro: procura-se "fila" no índice (em ordem alfabética) e obtém-se as páginas. Veja uma página (hipotética) do índice remissivo de um livro de Estruturas de Dados:
árvore
AVL, 112-125
B, 140-152
binária de busca, 98-111
busca
binária, 45-52
sequencial, 40-44
fila, 60-68
hash, tabela, 170-186
lista encadeada, 30-44
ordenação
merge sort, 210-218
quicksort, 219-228
pilha, 53-59, 201
- Cada termo (em ordem alfabética) é uma entrada do vocabulário.
- As páginas ao lado dele, em ordem crescente, são a posting list: a lista de "documentos" (páginas) que o contêm.
- Um termo pode aparecer em trechos separados, como "algoritmo": 12, 15 e 201.
- O sumário do início do livro faz o caminho contrário (capítulo → assuntos): é um índice direto.
1.1 Índice direto × índice invertido
Com uma coleção de 4 documentos (já sem a palavra "e"), cada documento recebe um número, o docID (D1 tem docID 1, D2 tem docID 2, e assim por diante):
| docID | Palavras do documento |
|---|---|
| 1 | gato, preto, branco |
| 2 | gato, branco |
| 3 | cachorro, preto |
| 4 | gato, cachorro |
| Termo | Posting list (docIDs) |
|---|---|
branco | 1 2 |
cachorro | 3 4 |
gato | 1 2 4 |
preto | 1 3 |
Para responder "quais documentos têm gato?" o índice direto obriga a olhar todas as linhas; o invertido responde com uma única entrada. O índice invertido tem dois componentes:
- Vocabulário (dicionário): a coleção dos termos distintos (
branco,cachorro,gato,preto), em ordem ou numa tabela hash. Cada termo aponta para sua lista. - Posting list (lista de ocorrências): para cada termo, os docIDs dos documentos que o contêm, em ordem crescente. Cada docID da lista é um posting (do inglês to post, "registrar"): o registro de que o termo ocorre naquele documento; por isso o nome posting list. Essa ordem é o que permitirá consultas rápidas (seção 3).
Ideia principal: pagar o custo uma única vez, ao construir o índice, para que cada consulta seja barata.
2. Construindo nosso primeiro índice invertido
Vamos construir, passo a passo, o índice da coleção abaixo (usaremos a palavra "e" como stopword). São 8 etapas, todas abertas para você acompanhar (e imprimir). Cada documento tem uma cor, para você ver de onde vem cada entrada da posting list.
| Palavra repetida no mesmo documento: no índice simples, um documento aparece uma única vez na lista de um termo, mesmo que a palavra apareça várias vezes nele. Se D2 fosse "Gato gato branco", o par (gato, 2) seria gerado duas vezes, mas na agregação a lista de "gato" teria só um 2. (Para registrar quantas vezes, existe o índice com frequência, na seção 4.) |
3. Consultando o índice invertido
Daqui em diante usamos o índice construído na seção 2:
| Termo | Posting list |
|---|---|
branco | 1 2 |
cachorro | 3 4 |
gato | 1 2 4 |
preto | 1 3 |
Toda consulta segue o mesmo caminho: (1) procurar cada termo no vocabulário; (2) obter suas posting lists; (3) combiná-las conforme o operador (AND, OR, NOT).
3.1 Busca por uma palavra
3.2 Consulta AND (interseção)
gato AND preto: queremos os documentos que contêm os dois termos, ou seja, os docIDs que aparecem nas duas listas.
Algoritmo (em alto nível): percorrer as duas listas ordenadas ao mesmo tempo, com um ponteiro em cada uma. Se os docIDs apontados são iguais, o documento entra no resultado; senão, avança o ponteiro do menor.
Custo: a cada comparação pelo menos um ponteiro avança e nenhum volta, então são no máximo m + n comparações, em que m e n são os tamanhos das duas listas: O(m + n).
3.3 Consulta OR (união)
gato OR preto: documentos que contêm pelo menos um dos termos.
Algoritmo (em alto nível): o mesmo percurso com dois ponteiros (como no merge do merge sort, Aula 21), mas agora todo docID visto vai para o resultado, e os repetidos entram uma só vez. Quando uma lista acaba, copia-se o resto da outra.
Custo: cada docID de cada lista é visitado uma vez: O(m + n).
3.4 Consulta NOT (diferença)
gato AND NOT preto: documentos que têm "gato" mas não têm "preto".
Algoritmo (em alto nível): o mesmo percurso com dois ponteiros, guardando os docIDs de L1 que não aparecem em L2.
Custo: O(m + n). Um NOT sozinho (NOT preto) devolveria quase toda a coleção; por isso os buscadores exigem pelo menos um termo positivo.
3.5 Consultas com três ou mais termos
gato AND preto AND branco: o AND combina duas listas por vez. Com três termos, fazemos duas interseções em sequência: o resultado da primeira vira uma das listas da segunda.
Ordem: começamos pelas listas menores. Os tamanhos são preto = 2, branco = 2 e gato = 3, então a ordem é preto, branco, gato.
Por que começar pelas menores? O resultado de uma interseção nunca é maior que a menor das listas, então começando por elas os resultados intermediários ficam pequenos. E se algum ficar vazio, o resultado final já é vazio e as listas restantes nem precisam ser lidas. Exemplo: em cachorro AND branco AND gato, a primeira interseção é cachorro [3, 4] AND branco [1, 2] = [], e a lista de gato nem chega a ser lida. Com listas de milhões de docIDs, evitar ler uma delas faz uma grande diferença.
4. Variações do índice invertido
A posting list pode guardar mais do que os docIDs, dependendo do que queremos responder. Para ver a diferença usamos a coleção anterior mais um documento, D5 = "gato preto gato" (com a palavra "gato" repetida), só nesta seção. Veja os três tipos de índice:
5. Busca por frases
Saber apenas que "gato" e "branco" estão no mesmo documento não basta para achar a expressão "gato branco": as palavras podem estar longe uma da outra. Precisamos saber onde cada palavra aparece, e é exatamente isso que o índice posicional da seção 4 guarda: a posição de cada ocorrência no texto (começando em 0). Veja os documentos D1 a D4 nesse formato:
| Doc | Texto (posições) | Entradas no índice |
|---|---|---|
| D1 | gato0 preto1 e2 branco3 | gato (1,[0]); preto (1,[1]); branco (1,[3]) |
| D2 | gato0 branco1 | gato (2,[0]); branco (2,[1]) |
| D3 | cachorro0 preto1 | cachorro (3,[0]); preto (3,[1]) |
| D4 | gato0 e1 cachorro2 | gato (4,[0]); cachorro (4,[2]) |
As posições são as do texto original: a stopword "e" não é indexada, mas continua ocupando a sua posição (por isso "branco" está na posição 3 em D1).
Consulta de frase: "gato branco" (as duas palavras, nessa ordem e lado a lado).
Trade-off das stopwords: ao não indexar "e", não conseguimos buscar a frase exata "gato e cachorro" (D4), porque a palavra do meio não está no índice. Uma saída é indexar também as stopwords (mais espaço); outra é aceitar distância 2 entre "gato" (0) e "cachorro" (2), aproximando a frase.
|
6. Representando o índice em C
Em C, o índice invertido básico precisa de apenas duas structs, que espelham os dois componentes da aula:
| Conceito da aula | Struct | O que guarda |
|---|---|---|
| posting list | PostingList | um vetor com os docIDs, em ordem crescente, e a quantidade n |
| entrada do vocabulário | Entrada | um termo e a sua PostingList |
O índice em si é só um vetor de Entrada, em ordem alfabética (o vocabulário): não precisa de uma struct à parte. Trocar esse vetor por uma hash, uma Trie ou uma B+-Tree (seção 7) não muda a PostingList.
#include <stdio.h> #include <string.h> #define MAX_DOCS 16 /* docIDs por posting list */ #define MAX_TERMOS 32 /* termos do vocabulario */ typedef struct { int docs[MAX_DOCS]; /* os docIDs, em ordem crescente */ int n; /* quantos docIDs */ } PostingList; typedef struct { char termo[32]; PostingList lista; } Entrada; /* uma entrada do vocabulario */ Entrada indice[MAX_TERMOS]; /* o indice: o vocabulario, em ordem alfabetica */ int nTermos; /* as operacoes recebem duas posting lists e devolvem uma */ PostingList lista_and(const PostingList *a, const PostingList *b); PostingList lista_or (const PostingList *a, const PostingList *b); PostingList lista_not(const PostingList *a, const PostingList *b); int main(void) { PostingList r; int i; /* monta "a mao" o indice do exemplo: gato -> [1, 2, 4] e preto -> [1, 3] */ strcpy(indice[0].termo, "gato"); indice[0].lista.docs[0] = 1; indice[0].lista.docs[1] = 2; indice[0].lista.docs[2] = 4; indice[0].lista.n = 3; strcpy(indice[1].termo, "preto"); indice[1].lista.docs[0] = 1; indice[1].lista.docs[1] = 3; indice[1].lista.n = 2; nTermos = 2; /* gato AND preto: entram duas posting lists, sai uma (a funcao e a da secao 3) */ r = lista_and(&indice[0].lista, &indice[1].lista); for (i = 0; i < r.n; i++) { printf("%d ", r.docs[i]); /* imprime: 1 */ } printf("\n"); return 0; }
Depois que o main monta o índice, a memória fica assim (o vetor indice, com nTermos = 2, e o resultado r do AND):
| posição no vetor | termo | lista.docs | lista.n |
|---|---|---|---|
indice[0] | "gato" | 1 2 4 | 3 |
indice[1] | "preto" | 1 3 | 2 |
r (resultado do AND) | — | 1 | 1 |
As operações da seção 3 (AND, OR, NOT) são funções que recebem duas posting lists e devolvem uma posting list, o que facilita encadeá-las, como na consulta com três termos. Para os índices com frequência e posicional (seção 4), em vez de um número, cada elemento do vetor guarda uma pequena struct com o docID, o tf (term frequency) e as posições; o restante da estrutura é igual.
7. Relação com as estruturas de dados estudadas
O índice invertido não é uma estrutura de dados isolada: é uma organização que combina estruturas que você já conhece. Seus dois componentes têm necessidades diferentes:
- Vocabulário: um conjunto de strings que precisa ser procurado a cada consulta ("onde está
gato?"), às vezes por prefixo ("termos que começam comca"). Aqui entram as estruturas das Aulas 19 a 23. - Posting lists: sequências de números ordenados que são percorridas do início ao fim pelos algoritmos de dois ponteiros. Um vetor (ou lista) ordenado, guardado de forma contígua, é o ideal.
| Estrutura | Como é utilizada no índice invertido | Por que utilizar? |
|---|---|---|
| Vetor ordenado | Vocabulário | Busca binária por termo |
| Tabela hash | Vocabulário | Busca exata muito rápida |
| Árvore AVL | Vocabulário | Busca e manutenção ordenada |
| Trie | Vocabulário | Busca por prefixos |
| Patrícia | Vocabulário | Trie compactada |
| TST (busca ternária) | Vocabulário | Busca por prefixos com menos memória que a Trie |
| B+-Tree | Vocabulário em disco | Busca eficiente em armazenamento secundário |
| Listas / vetores | Posting lists | Armazenar os documentos associados a cada termo |
Exemplo com o nosso vocabulário (branco, cachorro, gato, preto): para achar o termo "gato", uma tabela hash resolve em O(1). Já para sugerir termos a quem digitou "ca", o hash não ajuda: é preciso uma Trie/Patrícia (desce o "ca" e encontra "cachorro") ou uma B+-Tree (intervalo de "ca" até antes de "cb"). Depois de achar o termo, o índice entrega a posting list, que é percorrida pelos algoritmos da seção 3.
8. Análise de complexidade
m e n = tamanhos (número de docIDs) das posting lists envolvidas; |V| = número de termos do vocabulário; T = total de palavras da coleção (após normalização); c = número de letras de um termo.
| Operação | Pior caso | Caso médio | Em uma frase |
|---|---|---|---|
| Construção (ordenando os pares) | O(T log T) | O(T log T) | ordenar os T pares (termo, docID) com merge sort |
| Construção (vocabulário em hash) | O(T · |V|) | O(T) | um lookup (procura no vocabulário) por palavra; as listas já saem ordenadas |
| Busca de um termo | O(|V| + m) (hash) | O(1 + m) (hash) | localizar o termo + percorrer sua lista de m docIDs |
| AND | O(m + n) | O(m + n) | dois ponteiros, nenhum volta |
| OR | O(m + n) | O(m + n) | cada docID é visitado uma vez |
| NOT (A AND NOT B) | O(m + n) | O(m + n) | idem |
| Espaço | O(T) | menor que T | no máximo uma entrada por palavra da coleção (o índice posicional é maior) |
Por que a busca não percorre todos os documentos?
Porque o trabalho de olhar o texto dos documentos foi feito antes, na construção. Na consulta só tocamos nas posting lists dos termos da pergunta: com "gato" em 1.000 de 10 milhões de páginas, são ~1.000 leituras, e não 10 bilhões.
Localizar o termo × percorrer a lista
São dois custos distintos: (1) achar o termo no vocabulário, que depende da estrutura escolhida: O(1) com hash; O(c) com Trie, em que c é o número de letras do termo; O(log |V|) com vetor ordenado, em que |V| é o número de termos do vocabulário. (2) percorrer a lista, que custa O(m), em que m é o número de docIDs da lista. Para termos muito comuns, quem domina é o (2).
Por que AND e OR custam O(m + n)?
A cada comparação pelo menos um ponteiro avança e nenhum volta. Como o ponteiro i anda no máximo m posições e o j no máximo n, são no máximo m + n comparações. No pior caso as listas se intercalam (como [1, 3, 5] e [2, 4, 6]): cada passo avança um só ponteiro. No caso médio o custo é da mesma ordem; só pode terminar antes se uma lista acabar antes da outra.
Por que manter as listas ordenadas é tão importante?
Com as listas ordenadas, o algoritmo dos dois ponteiros resolve AND, OR e NOT em O(m + n). Sem ordenação, para cada elemento de L1 teríamos que procurar em toda a L2: O(m × n). Com 1.000 e 1.000.000 de docIDs, isso é 109 comparações contra ~106.
9. Resumo da aula
- O que é: um índice invertido associa cada termo (vocabulário) à lista ordenada dos documentos que o contêm (posting list): palavra → documentos.
- Como se constrói: tokenização, normalização, remoção de stopwords, geração dos pares (termo, docID), ordenação e agrupamento, em O(T log T) (T = total de palavras da coleção).
- Como se consulta: procurar o termo no vocabulário, obter a lista e combinar listas com AND (interseção), OR (união) e NOT (diferença).
- Por que as listas são ordenadas: permitem o algoritmo de dois ponteiros, que faz AND, OR e NOT em O(m + n) em vez de O(m × n) (m e n = tamanhos das duas listas); em consultas com vários termos, começa-se pelas listas menores.
- Estruturas de dados: o vocabulário usa hash (busca exata), Trie/Patrícia (prefixos) ou B+-Tree (disco); as posting lists são vetores ordenados. O índice posicional acrescenta as posições e permite buscar frases.
10. Exercícios
Nos exercícios, use a coleção: E1 = "Sol e lua.", E2 = "Lua azul.", E3 = "Sol azul e quente.", E4 = "Lua quente." (stopword: "e").
-
Construa o índice invertido da coleção, mostrando as etapas (tokenização, normalização, remoção da stopword, pares, ordenação e agrupamento).
-
AND: calcule
lua AND quentepelo algoritmo dos dois ponteiros, mostrando cada passo. -
OR: calcule
sol OR azul, mostrando cada passo. -
NOT: calcule
lua AND NOT azul, mostrando cada passo. -
Três termos: calcule
quente AND azul AND lua. Em que ordem você faz as interseções e por quê? -
Frases: escreva o índice posicional (com as posições do texto original) e responda: quais documentos contêm a frase
"sol azul"? E"sol quente"? -
Por que "invertido"? O que seria um índice "direto" (não invertido)? Escreva o índice direto da coleção.
-
Trade-off de stopwords: por que remover stopwords como "e" é um trade-off? O que se perde?
-
Estruturas: por que a consulta
"qu*"(autocompletar) não funciona com o vocabulário numa tabela hash? Que estruturas das Aulas 22 e 23 resolvem o problema, e com que custo? -
Varredura linear × índice invertido: compare o desempenho para uma consulta em 10 milhões de documentos onde o termo aparece em 1.000 deles. Suponha 1.000 palavras por documento e que ler uma palavra custa 1 unidade de tempo.
Gabaritos
Sugestão de resposta — Exercício 1
| Etapa | Resultado |
|---|---|
| Tokenização | E1: Sol | e | lua. E2: Lua | azul. E3: Sol | azul | e | quente. E4: Lua | quente. |
| Normalização | E1: sol e lua E2: lua azul E3: sol azul e quente E4: lua quente |
| Sem stopword "e" | E1: sol lua E2: lua azul E3: sol azul quente E4: lua quente |
| Pares (termo, docID) | (sol,1) (lua,1) (lua,2) (azul,2) (sol,3) (azul,3) (quente,3) (lua,4) (quente,4) |
| Ordenados | (azul,2) (azul,3) (lua,1) (lua,2) (lua,4) (quente,3) (quente,4) (sol,1) (sol,3) |
| Índice (agrupado) | azul → [2, 3]; lua → [1, 2, 4]; quente → [3, 4]; sol → [1, 3] |
Sugestão de resposta — Exercício 2
Resultado: [4]: só E4 ("Lua quente.") tem os dois termos.
Sugestão de resposta — Exercício 3
Resultado: [1, 2, 3]. O docID 3 está nas duas listas e sai uma só vez.
Sugestão de resposta — Exercício 4
Resultado: [1, 4]: documentos com "lua" que não têm "azul".
Sugestão de resposta — Exercício 5
Tamanhos: quente = 2, azul = 2, lua = 3. Começamos pelas menores (quente e azul):
quente 3 4
AND
azul 2 3
=
3
lua 1 2 4
=
(vazio)
Resultado: []. Começar pelas menores mantém os resultados parciais pequenos e permite parar assim que um deles ficar vazio, sem ler as demais listas.
Sugestão de resposta — Exercício 6
| Termo | Entradas (docID, [posições]) |
|---|---|
azul | (2,[1]), (3,[1]) |
lua | (1,[2]), (2,[0]), (4,[0]) |
quente | (3,[3]), (4,[1]) |
sol | (1,[0]), (3,[0]) |
"sol azul": sol [1, 3] ∩ azul [2, 3] = [3]. Em E3, sol está na posição 0 e azul na 1: adjacentes. Resultado: [3].
"sol quente": sol [1, 3] ∩ quente [3, 4] = [3]. Em E3, sol está na posição 0 e quente na 3 (a posição 2 é o "e" removido): diferença 3 ≠ 1. Resultado: [].
Sugestão de resposta — Exercício 7
O índice direto associa cada documento às palavras que ele contém: E1 → [sol, lua], E2 → [lua, azul], E3 → [sol, azul, quente], E4 → [lua, quente]. Para saber quais documentos têm "lua" é preciso olhar todas as linhas.
O índice invertido inverte a relação (palavra → documentos): basta uma entrada, lua → [1, 2, 4].
Sugestão de resposta — Exercício 8
Ganhos: stopwords aparecem em quase todos os documentos, então suas posting lists seriam enormes e pouco úteis; removê-las reduz o espaço e o tempo das interseções.
Perdas: frases exatas que contêm stopwords deixam de poder ser buscadas (como "gato e cachorro") e a busca pela própria stopword fica impossível.
Sugestão de resposta — Exercício 9
A hash espalha os termos sem preservar semelhança: "quente" e "queijo" caem em posições sem relação. Para achar os termos que começam com "qu" seria preciso testar todos os |V| termos.
Trie / Patrícia (Aula 22): desce as 2 letras do prefixo e coleta a subárvore: O(p + t), com p = tamanho do prefixo e t = nós visitados abaixo dele.
B+-Tree (Aula 23): os termos com o prefixo formam uma faixa contínua da ordem alfabética: desce até a primeira folha, O(logt |V|) leituras, e segue a lista encadeada de folhas até sair da faixa.
Sugestão de resposta — Exercício 10
Varredura linear: 10.000.000 × 1.000 = 10 bilhões de leituras (~10 s a 109 leituras/s).
Índice invertido: um lookup + a leitura da lista de 1.000 docIDs: ~1.000 operações.
Melhoria: 1010 / 103 = 10 milhões de vezes. O custo do índice depende de quantos documentos contêm o termo, e não do tamanho da coleção.
Conteúdo complementar (opcional): compressão das posting lists
Em coleções reais as posting lists são enormes, então elas são comprimidas. Como os docIDs são ordenados, guardamos as diferenças (gaps) entre docIDs consecutivos, que são números pequenos e cabem em menos bits (por exemplo, com a codificação VByte, de tamanho variável):
| Posting list | Valores | |||||||
|---|---|---|---|---|---|---|---|---|
| docIDs originais | 1 | 2 | 4 | 7 | 11 | 23 | 47 | 89 |
| gaps | 1 | 1 | 2 | 3 | 4 | 12 | 24 | 42 |
Todos os gaps cabem em 1 byte: 8 bytes contra 8 × 4 = 32 bytes com docIDs de 32 bits. Os docIDs originais são recuperados somando os gaps. Esse tema não é cobrado nesta aula.