Construindo um Índice Invertido em Elixir: do zero ao TF-IDF

Você já parou para pensar em como o Google, o Elasticsearch ou o Lucene conseguem encontrar documentos relevantes em milissegundos, mesmo com bilhões de páginas indexadas?

A resposta está em uma estrutura de dados elegante chamada índice invertido. E a boa notícia é que você pode implementá-la do zero em Elixir em menos de 100 linhas.

Neste artigo, vamos construir passo a passo um índice invertido, adicionar busca booleana (AND/OR), calcular frequência de termos (TF) e, por fim, ranquear resultados com TF-IDF.

O que é um índice invertido?

Se você pensar em um livro, o índice remissivo no final lista cada termo importante e as páginas onde ele aparece. Um índice invertido faz exatamente isso, mas para documentos:

"o gato subiu no telhado"   → doc 1
"o cachorro latiu"          → doc 2

Índice invertido:
%{
  "gato"     => [1],
  "subiu"    => [1],
  "telhado"  => [1],
  "cachorro" => [2],
  "latiu"    => [2]
}

Em vez de, para cada busca, varrer todos os documentos (custo O(n)), consultamos diretamente o mapa de termos — custo praticamente O(1).

Simples, né? Vamos codar.

Preparando o projeto

mix new indice_invertido
cd indice_invertido

Nada de dependências externas — só Elixir puro.

Passo 1: Tokenização

Antes de indexar, precisamos transformar texto bruto em tokens limpos: minúsculas, sem pontuação, sem stopwords. Esse é o trabalho da função tokenizar/1, e o módulo abaixo documenta cada decisão.

defmodule IndiceInvertido do
  @moduledoc """
  Módulo responsável por transformar texto bruto em tokens normalizados,
  etapa fundamental para a construção de um índice invertido.

  A função principal é `tokenizar/1`, que recebe uma string e devolve
  uma lista de tokens limpos — sem pontuação, sem maiúsculas e sem
  stopwords.

  ## O que são stopwords

  Stopwords são palavras tão comuns em um idioma que não ajudam a
  distinguir documentos entre si. Em português, palavras como "a",
  "o", "de", "para" aparecem em praticamente todo texto e, por isso,
  são descartadas durante a indexação. Mantê-las só aumentaria o
  tamanho do índice sem melhorar a qualidade da busca.

  As stopwords deste módulo são declaradas como atributo de módulo:

      @stopwords ~w(a o e de da do em no na um uma para com por que se)

  O sigil `~w(...)` (word list) é um atalho para criar uma lista de
  strings. Estas duas linhas são equivalentes:

      ~w(a o e de)
      ["a", "o", "e", "de"]

  ## Pipeline de tokenização

  A função `tokenizar/1` aplica quatro transformações em sequência,
  encadeadas com o operador pipe `|>`. O pipe pega o resultado da
  esquerda e passa como primeiro argumento da função da direita.
  Ou seja, `texto |> String.downcase()` é o mesmo que
  `String.downcase(texto)`.

  ### Etapa 1 — `String.downcase/1`

  Converte todo o texto para minúsculas, garantindo que "Gato",
  "gato" e "GATO" sejam tratados como o mesmo token.

      iex> String.downcase("O GATO Subiu")
      "o gato subiu"

  A função lida corretamente com caracteres acentuados:

      iex> String.downcase("AÇÃO")
      "ação"

  ### Etapa 2 — `String.replace/3` com o regex `~r/[^\\p{L}\\p{N}\\s]/u`

  Remove pontuação, símbolos e emojis, substituindo cada caractere
  indesejado por um espaço. O regex merece atenção:

    * `[^...]` — classe negada: "qualquer coisa que NÃO seja..."
    * `\\p{L}`  — qualquer letra Unicode (inclui `ç`, `é`, `日`)
    * `\\p{N}`  — qualquer número Unicode (inclui `0-9`)
    * `\\s`    — qualquer espaço em branco (espaço, tab, quebra de linha)
    * `/u`     — flag Unicode, indispensável para `\\p{...}` funcionar

  Em português: *casa com qualquer caractere que não seja letra,
  número ou espaço em branco*.

      iex> String.replace("olá, mundo!", ~r/[^\\p{L}\\p{N}\\s]/u, " ")
      "olá  mundo "

  A substituição é feita por **espaço**, e não por string vazia.
  Isso é importante: se apagássemos direto, `"fim.início"` viraria
  `"fimíncio"` (grudado). Com espaço, os termos permanecem separados.

      iex> String.replace("fim.início", ~r/[^\\p{L}\\p{N}\\s]/u, "")
      "fimíncio"

      iex> String.replace("fim.início", ~r/[^\\p{L}\\p{N}\\s]/u, " ")
      "fim início"

  Note que esta etapa pode gerar espaços duplos, o que é tratado
  na próxima.

  ### Etapa 3 — `String.split/3` com o regex `~r/\\s+/` e `trim: true`

  Divide a string em uma lista de tokens. O regex `\\s+` casa com
  um ou mais espaços em branco seguidos, então espaços duplos são
  tratados como um único separador. A opção `trim: true` descarta
  strings vazias no início e no final.

      iex> String.split("  olá  mundo  ", ~r/\\s+/)
      ["", "olá", "mundo", ""]

      iex> String.split("  olá  mundo  ", ~r/\\s+/, trim: true)
      ["olá", "mundo"]

  ### Etapa 4 — `Enum.reject/2` com o capture `&`

  Descarta os tokens que estão na lista de stopwords. `Enum.reject/2`
  percorre a lista e remove os elementos para os quais a função
  retorna `true` — é o oposto de `Enum.filter/2`.

      iex> Enum.reject([1, 2, 3, 4], fn x -> x > 2 end)
      [1, 2]

  O capture `&(&1 in @stopwords)` é uma forma abreviada de criar uma
  função anônima. `&1` refere-se ao primeiro argumento. Estas duas
  linhas são idênticas:

      Enum.reject(lista, &(&1 in @stopwords))
      Enum.reject(lista, fn token -> token in @stopwords end)

  O operador `in` testa se um item pertence a uma coleção:

      iex> "gato" in ["a", "o", "gato"]
      true

  ## Resultado final

      iex> IndiceInvertido.tokenizar("O gato subiu no telhado!")
      ["gato", "subiu", "telhado"]

      iex> IndiceInvertido.tokenizar("Ela comprou 3 maçãs, 2 peras e 1 banana!")
      ["ela", "comprou", "3", "maçãs", "2", "peras", "1", "banana"]

  Note que números são preservados por causa de `\\p{N}` no regex.
  """

  @stopwords ~w(a o e de da do em no na um uma para com por que se)

  def tokenizar(texto) do
    texto
    |> String.downcase()
    |> String.replace(~r/[^\p{L}\p{N}\s]/u, " ")
    |> String.split(~r/\s+/, trim: true)
    |> Enum.reject(&(&1 in @stopwords))
  end
end

Repare no uso de \p{L} e \p{N} com a flag u — isso garante que acentos como é e ã sejam preservados. Um detalhe importante ao trabalhar com português.

Teste rápido:

iex> IndiceInvertido.tokenizar("O gato subiu no telhado!")
["gato", "subiu", "telhado"]

Passo 2: Construindo o índice

Agora a parte central. Recebemos um mapa %{doc_id => texto} e retornamos %{termo => [doc_ids]}.

def construir(documentos) when is_map(documentos) do
  documentos
  |> Enum.flat_map(fn {doc_id, texto} ->
    texto
    |> tokenizar()
    |> Enum.uniq()
    |> Enum.map(fn termo -> {termo, doc_id} end)
  end)
  |> Enum.group_by(fn {termo, _} -> termo end, fn {_, doc_id} -> doc_id end)
  |> Map.new(fn {termo, docs} -> {termo, Enum.sort(docs)} end)
end

Vamos destrinchar linha a linha.

documentos |> Enum.flat_map(fn {doc_id, texto} -> ... end)

Enum.flat_map/2 percorre o mapa e, para cada par {doc_id, texto}, aplica a função — mas achata o resultado em uma única lista. Se cada documento gera uma lista de pares, o flat_map junta tudo em uma lista só, em vez de uma lista de listas.

iex> Enum.flat_map(%{1 => "a b", 2 => "c d"}, fn {id, txt} ->
...>   Enum.map(String.split(txt), fn t -> {t, id} end)
...> end)
[{"a", 1}, {"b", 1}, {"c", 2}, {"d", 2}]

Sem o flat_map (usando map), o resultado seria [[{"a", 1}, {"b", 1}], [{"c", 2}, {"d", 2}]] — mais chato de processar depois.

Enum.uniq() e Enum.map(fn termo -> {termo, doc_id} end)

tokenizar/1 devolve os tokens na ordem em que aparecem, com repetições. Se "gato" aparece três vezes no mesmo documento, não queremos três pares {"gato", 1} no índice — queremos um só.

iex> ["gato", "gato", "telhado"] |> Enum.uniq()
["gato", "telhado"]

Depois, Enum.map/2 transforma cada token em uma tupla {termo, doc_id}, preparando os pares que serão agrupados.

Enum.group_by/3

Enum.group_by/3 agrupa os pares pela chave (o termo) e coleta os valores (os doc_id) em listas.

iex> [{"gato", 1}, {"gato", 2}, {"telhado", 1}]
...> |> Enum.group_by(fn {termo, _} -> termo end, fn {_, id} -> id end)
%{"gato" => [1, 2], "telhado" => [1]}

O primeiro argumento é a função que extrai a chave. O segundo é a função que extrai o valor a ser coletado.

Map.new/2 com Enum.sort

Map.new/2 reconstrói o mapa garantindo que os IDs de cada termo estejam ordenados. A ordenação ajuda nas interseções do próximo passo (busca AND), que funcionam melhor com listas ordenadas.

iex> %{"gato" => [3, 1, 2]} |> Map.new(fn {t, docs} -> {t, Enum.sort(docs)} end)
%{"gato" => [1, 2, 3]}

Testando

docs = %{
  1 => "O gato subiu no telhado",
  2 => "O cachorro latiu para o gato",
  3 => "O telhado é de barro"
}

indice = IndiceInvertido.construir(docs)
# %{
#   "barro"    => [3],
#   "cachorro" => [2],
#   "gato"     => [1, 2],
#   "latiu"    => [2],
#   "subiu"    => [1],
#   "telhado"  => [1, 3]
# }

Passo 3: Busca booleana (AND / OR)

Um índice sem busca é só um mapa bonito. Vamos consultá-lo.

Busca OR

Encontra documentos que contenham qualquer termo da consulta:

def buscar_or(indice, consulta) do
  consulta
  |> tokenizar()
  |> Enum.flat_map(&Map.get(indice, &1, []))
  |> Enum.uniq()
  |> Enum.sort()
end

Aqui reutilizamos tokenizar/1 na consulta — o mesmo tratamento aplicado aos documentos é aplicado à busca. Isso garante que "GATO" na query vire "gato" e case com o índice.

Enum.flat_map(&Map.get(indice, &1, [])) busca cada termo no índice. O [] como padrão evita que um termo desconhecido quebre a busca — se a palavra não existe no índice, ela contribui com uma lista vazia.

iex> indice = %{"gato" => [1, 2], "barro" => [3]}
iex> ["gato", "barro"] |> Enum.flat_map(&Map.get(indice, &1, []))
[1, 2, 3]

iex> ["gato", "inexistente"] |> Enum.flat_map(&Map.get(indice, &1, []))
[1, 2]

Depois, Enum.uniq/1 remove duplicatas (um documento que contém os dois termos só aparece uma vez) e Enum.sort/1 mantém a ordem consistente.

Busca AND

Encontra documentos que contenham todos os termos:

def buscar_and(indice, consulta) do
  consulta
  |> tokenizar()
  |> Enum.map(&Map.get(indice, &1, []))
  |> intersecao()
end

defp intersecao([]), do: []
defp intersecao([lista | resto]), do: Enum.reduce(resto, lista, &(&2 -- (&2 -- &1)))

Aqui usamos Enum.map/2 (não flat_map), porque queremos preservar cada lista de documentos separada — vamos intersectá-las.

A função intersecao/1 tem duas cláusulas:

• intersecao([]) — caso base: lista vazia retorna lista vazia.
• intersecao([lista | resto]) — pega a primeira lista e a usa como acumulador inicial do reduce.

A expressão &2 -- (&2 -- &1) calcula a interseção de duas listas usando apenas o operador -- (diferença de listas):

• &2 -- &1 remove de &2 os elementos que estão em &1.
• &2 -- (&2 -- &1) remove de &2 os elementos que não estão em &1 — sobrando exatamente a interseção.

iex> [1, 2, 3] -- [1, 2, 3] -- [2, 3]
[2, 3]

Por isso ordenamos as listas no passo anterior: a interseção por diferença de listas depende da ordem dos elementos.

Uso

IndiceInvertido.buscar_and(indice, "gato telhado")  # => [1]
IndiceInvertido.buscar_or(indice, "gato barro")     # => [1, 2, 3]

Passo 4: Frequência de termos e posições

Um índice que só diz "sim/não" não ranqueia nada. Para melhorar, guardamos quantas vezes o termo aparece em cada documento e onde.

def construir_com_tf(documentos) do
  documentos
  |> Enum.flat_map(fn {doc_id, texto} ->
    texto
    |> tokenizar_com_posicao()
    |> Enum.map(fn {termo, pos} -> {termo, doc_id, pos} end)
  end)
  |> Enum.group_by(fn {termo, _, _} -> termo end)
  |> Map.new(fn {termo, ocorrencias} ->
    docs =
      ocorrencias
      |> Enum.group_by(fn {_, doc_id, _} -> doc_id end)
      |> Map.new(fn {doc_id, lista} ->
        posicoes = Enum.map(lista, fn {_, _, pos} -> pos end)
        {doc_id, %{tf: length(posicoes), posicoes: posicoes}}
      end)

    {termo, docs}
  end)
end

defp tokenizar_com_posicao(texto) do
  texto
  |> String.downcase()
  |> String.replace(~r/[^\p{L}\p{N}\s]/u, " ")
  |> String.split(~r/\s+/, trim: true)
  |> Enum.reject(&(&1 in @stopwords))
  |> Enum.with_index()
end

Vamos por partes.

tokenizar_com_posicao/1

É a mesma tokenizar/1, mas com Enum.with_index() no final. Essa função transforma cada elemento da lista em uma tupla {elemento, índice}:

iex> ["gato", "subiu", "telhado"] |> Enum.with_index()
[{"gato", 0}, {"subiu", 1}, {"telhado", 2}]

Agora cada token carrega sua posição no documento — informação que permite busca por frase mais adiante.

Primeiro flat_map — desmembrando

Para cada documento, geramos uma lista de triplas {termo, doc_id, posicao}:

iex> %{1 => "gato gato telhado"} 
...> |> Enum.flat_map(fn {id, txt} ->
...>   txt |> String.split() |> Enum.with_index() |> Enum.map(fn {t, p} -> {t, id, p} end)
...> end)
[{"gato", 1, 0}, {"gato", 1, 1}, {"telhado", 1, 2}]

Repare que "gato" aparece duas vezes — e é isso que queremos, porque a repetição é a informação de frequência.

Primeiro group_by — agrupando por termo

Agrupamos todas as triplas pelo termo. Note o padrão {termo, _, _} — usamos _ para ignorar o doc_id e a posição, já que estamos agrupando apenas pelo termo.

iex> [{"gato", 1, 0}, {"gato", 1, 1}, {"telhado", 1, 2}]
...> |> Enum.group_by(fn {termo, _, _} -> termo end)
%{
  "gato"    => [{"gato", 1, 0}, {"gato", 1, 1}],
  "telhado" => [{"telhado", 1, 2}]
}

Segundo group_by dentro do Map.new

Para cada termo, precisamos agrupar as ocorrências por documento. O padrão {_, doc_id, _} ignora o termo e a posição.

iex> [{"gato", 1, 0}, {"gato", 1, 1}, {"gato", 2, 5}]
...> |> Enum.group_by(fn {_, doc_id, _} -> doc_id end)
%{
  1 => [{"gato", 1, 0}, {"gato", 1, 1}],
  2 => [{"gato", 2, 5}]
}

Agora, dentro do Map.new/2 mais interno, extraímos apenas as posições e calculamos o tf (quantas ocorrências o termo teve naquele documento):

posicoes = Enum.map(lista, fn {_, _, pos} -> pos end)
{doc_id, %{tf: length(posicoes), posicoes: posicoes}}

O length(posicoes) é o term frequency para aquele par termo/documento. O posicoes guarda onde o termo apareceu, permitindo busca por frase depois.

Resultado

Agora o índice fica mais rico:

iex> indice["gato"]
%{
  1 => %{tf: 1, posicoes: [1]},
  2 => %{tf: 1, posicoes: [5]}
}

Com as posições, você pode até implementar busca por frase — basta verificar se as posições dos termos são adjacentes.

Passo 5: Ranking com TF-IDF

Agora o pulo do gato (trocadilho inevitável). TF-IDF é uma métrica clássica que combina:

• TF (Term Frequency): quanto mais o termo aparece no documento, mais relevante ele é para aquele documento.
• IDF (Inverse Document Frequency): quanto mais raro o termo no corpus inteiro, mais informativo ele é.

Palavras como "de" aparecem em tudo — IDF baixo. Palavras como "criptografia" aparecem em poucos documentos — IDF alto.

def buscar_ranqueado(indice, total_docs, consulta) do
  termos = tokenizar(consulta)

  scores =
    Enum.reduce(termos, %{}, fn termo, acc ->
      case Map.get(indice, termo) do
        nil -> acc
        docs ->
          idf = :math.log(total_docs / map_size(docs))
          Enum.reduce(docs, acc, fn {doc_id, %{tf: tf}}, a ->
            Map.update(a, doc_id, tf * idf, &(&1 + tf * idf))
          end)
      end
    end)

  scores
  |> Enum.sort_by(fn {_doc, score} -> -score end)
  |> Enum.map(fn {doc_id, score} -> {doc_id, Float.round(score, 3)} end)
end

Enum.reduce(termos, %{}, fn termo, acc -> ... end)

Percorremos cada termo da consulta, acumulando um mapa %{doc_id => score}. O acumulador começa vazio e vai sendo atualizado termo a termo.

case Map.get(indice, termo) do ... end

Se o termo não existe no índice, Map.get retorna nil e simplesmente mantemos o acumulador. Se existe, calculamos a contribuição dele.

idf = :math.log(total_docs / map_size(docs))

O IDF é o logaritmo natural da razão entre o total de documentos e o número de documentos que contêm o termo. map_size(docs) conta quantos documentos (chaves) o termo tem.

iex> :math.log(3 / 2)
0.4054651081081644

iex> :math.log(3 / 1)
1.0986122886681098

Um termo que aparece em 1 de 3 documentos tem IDF maior que um que aparece em 2 de 3 — confirmando que termos raros são mais informativos.

Enum.reduce(docs, acc, fn {doc_id, %{tf: tf}}, a -> ... end)

Para cada documento onde o termo aparece, desestruturamos o padrão %{tf: tf} — pattern matching direto na cabeça do fn, extraindo o tf do mapa.

Map.update(a, doc_id, tf * idf, &(&1 + tf * idf))

Map.update/4 atualiza o score do documento:

• Se o doc_id ainda não está no mapa, insere com valor tf * idf.
• Se já está (o documento tem mais de um termo da consulta), soma tf * idf ao valor existente com a função &(&1 + tf * idf).

É por isso que documentos que contêm todos os termos da consulta acumulam score maior.

Ordenação

|> Enum.sort_by(fn {_doc, score} -> -score end)

Enum.sort_by/2 ordena pelos scores, mas com -score invertemos — do maior para o menor. Sem isso, seria ordem crescente.

Uso

indice = IndiceInvertido.construir_com_tf(docs)
IndiceInvertido.buscar_ranqueado(indice, 3, "gato telhado")
# => [{1, 0.811}, {2, 0.405}]

Documentos que contêm os dois termos pontuam mais alto — exatamente o que esperamos.

Passo 6: Testes

Nenhum tutorial sério termina sem testes. Com ExUnit:

defmodule IndiceInvertidoTest do
  use ExUnit.Case
  alias IndiceInvertido, as: II

  @docs %{
    1 => "O gato subiu no telhado",
    2 => "O cachorro latiu para o gato"
  }

  test "constrói índice básico" do
    indice = II.construir(@docs)
    assert indice["gato"] == [1, 2]
    assert indice["cachorro"] == [2]
  end

  test "busca AND" do
    indice = II.construir(@docs)
    assert II.buscar_and(indice, "gato cachorro") == [2]
    assert II.buscar_and(indice, "gato telhado") == [1]
  end

  test "busca OR" do
    indice = II.construir(@docs)
    assert II.buscar_or(indice, "cachorro telhado") == [1, 2]
  end
end

O alias IndiceInvertido, as: II permite referenciar o módulo como II nos testes, deixando o código mais curto. O @docs é um atributo de módulo — uma constante compartilhada entre os testes.

Rode com mix test e pronto.

Onde ir a partir daqui

O que construímos é a fundação. Alguns caminhos naturais para evoluir:

• Stemming em português — reduzir gatos → gato com a lib stemmer.
• GenServer — encapsular o índice em um processo para consultas concorrentes.
• Task.async_stream — paralelizar a indexação de milhares de documentos.
• Persistência — usar :dets, :ets ou :mnesia para não reconstruir o índice a cada boot.
• Busca por frase — usando as posições que já guardamos.

Conclusão

Índice invertido é uma daquelas estruturas que parecem mágica até você escrever a sua. Em Elixir, o poder do Enum, Map e pattern matching torna a implementação surpreendentemente enxuta e legível.

O código completo está no GitHub — fique à vontade para fazer fork e experimentar.

E você? Já usou índices invertidos em algum projeto? Conta aqui nos comentários o que achou — e se quiser, no próximo artigo posso mostrar como transformar isso num servidor GenServer concorrente.