Início › Explorações › Motor de Busca
Exploração

🔍 Como um motor de busca funciona

Pesquisar em bilhões de páginas em menos de 1 segundo parece impossível — mas é resultado de uma estrutura de dados simples e engenhosa: o índice invertido. Em vez de varrer todos os documentos a cada busca, o índice mapeia cada palavra para a lista de documentos que a contém. Construa um abaixo e faça consultas.

① Intuição

Imagine o índice remissivo de um livro: no final, cada conceito aponta para as páginas onde aparece. Um motor de busca é exatamente isso — um índice remissivo gigante, construído para todas as palavras de todos os documentos.

A busca por "gato" não percorre todos os documentos — vai diretamente ao índice, encontra a entrada "gato" e retorna a lista de documentos. O custo é O(1) por palavra, independente de quantos bilhões de documentos existam.

② Visualização — construa e consulte

Clique em "Construir índice" para ver o processo de tokenização e indexação documento a documento. Depois faça consultas com uma ou mais palavras.

📚
4 documentos aguardando indexação
D1
Gato no telhado
D2
Cachorro e gato
D3
O telhado caiu
D4
Cachorro perdido

③ Explicação técnica

Passo 1 — Tokenização

Antes de indexar, cada documento é quebrado em tokens normalizados. Stop words (palavras muito comuns sem valor semântico) são removidas:

import re

STOP_WORDS = {"o", "a", "e", "de", "do", "da", "em", "no", "na", "um"}

def tokenize(text: str) -> list[str]:
    # 1. Caixa baixa
    text = text.lower()
    # 2. Remover pontuação
    text = re.sub(r'[^\w\s]', ' ', text)
    # 3. Separar por espaço
    tokens = text.split()
    # 4. Remover stop words
    return [t for t in tokens if t not in STOP_WORDS]

tokenize("O gato subiu no telhado!")
# → ["gato", "subiu", "telhado"]

Passo 2 — Construção do índice

Para cada token, adicionamos o ID do documento à lista de postings:

from collections import defaultdict

def build_index(docs: list[dict]) -> dict:
    index = defaultdict(list)   # palavra → [doc_ids]

    for doc in docs:
        tokens = tokenize(doc["text"])
        for token in set(tokens):          # set: evita duplicar doc
            index[token].append(doc["id"])

    return dict(index)

# index["gato"] → ["D1", "D2"]
# index["telhado"] → ["D1", "D3"]

Passo 3 — Consulta

Busca simples é um lookup no dicionário. Busca com múltiplos termos é a interseção das listas (operação AND):

def search(index: dict, query: str) -> list[str]:
    terms = tokenize(query)
    if not terms:
        return []

    # Busca um termo: lookup O(1)
    if len(terms) == 1:
        return index.get(terms[0], [])

    # Múltiplos termos: interseção de listas
    sets = [set(index.get(t, [])) for t in terms]
    result = sets[0]
    for s in sets[1:]:
        result = result & s     # AND: docs que têm todos os termos
    return list(result)

search(index, "gato telhado")  # → ["D1"]
search(index, "cachorro")      # → ["D2", "D4"]

Passo 4 — Ranking com TF-IDF

Encontrar documentos é só metade — eles precisam ser ordenados por relevância. TF-IDF (Term Frequency × Inverse Document Frequency) é a base histórica do ranking:

import math

def tf_idf(term, doc_id, docs, index):
    # TF: frequência do termo no documento
    doc_text = next(d["text"] for d in docs if d["id"] == doc_id)
    tokens = tokenize(doc_text)
    tf = tokens.count(term) / len(tokens)

    # IDF: raridade do termo na coleção
    n_docs = len(docs)
    n_with_term = len(index.get(term, []))
    idf = math.log(n_docs / (1 + n_with_term))

    return tf * idf

# Documentos com TF-IDF alto aparecem primeiro nos resultados

Complexidade

OperaçãoCusto
Lookup de 1 termoO(1) — hash table
Interseção AND de k termosO(k × menor lista)
Indexação de 1 documentoO(n_tokens)
Busca linear (sem índice)O(n_docs × n_tokens)

④ Projeto

Motor de busca para arquivos locais:

  1. Leia todos os arquivos .txt de uma pasta com pathlib
  2. Tokenize e construa o índice invertido
  3. Implemente um REPL que aceita queries e mostra os arquivos correspondentes
  4. Adicione ranking por TF-IDF e mostre os 5 mais relevantes
  5. Bônus: suporte a busca por frase exata com "aspas"

⑤ Perguntas rápidas

⑥ Aplicações no mundo real