💬 NLP

Frequency-Ordered Tokenization for Better Text Compression

O artigo apresenta a "tokenização ordenada por frequência", uma técnica simples de pré-processamento que melhora a compressão de texto sem perdas ao reordenar o vocabulário com base na Lei de Zipf, resultando em ganhos significativos de taxa de compressão e velocidade em comparação com métodos tradicionais.

Autores originais: Maximilian Kalcher

Publicado 2026-02-27

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Maximilian Kalcher

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você tem uma pilha gigante de livros (seja em inglês, chinês ou árabe) e precisa enviá-los para um amigo pelo correio, mas o frete é cobrado por peso. O objetivo é fazer esses livros ficarem o mais leves possível sem perder nenhuma página.

A maioria das pessoas tenta dobrar os livros ou usar caixas menores (os algoritmos de compressão tradicionais). Mas este artigo propõe uma ideia diferente: antes de empacotar, vamos reorganizar as palavras de uma forma inteligente.

Aqui está a explicação do método "Tokenização Ordenada por Frequência" usando analogias do dia a dia:

1. O Problema: A Lei de Zipf (A Regra do "Mais Usado")

Em qualquer idioma, algumas palavras ou partes de palavras são usadas o tempo todo (como "o", "a", "de", "e"), enquanto outras são raras (como "espectroscopia" ou "quimera"). Isso é chamado de Lei de Zipf.

A analogia: Imagine que você tem um baú de peças de Lego. Você tem 1.000 peças vermelhas (comuns) e apenas 1 peça dourada (rara). Se você tentar empacotar tudo misturado, o caminhão fica cheio de "espaço vazio" porque está tentando lidar com a complexidade de todas as peças ao mesmo tempo.

2. A Solução: O Método de "Reorganização Inteligente"

Os autores propõem três passos simples para "desenhar" os livros antes de enviá-los:

Passo A: Quebrar em "Blocos" (Tokenização BPE)

Em vez de tratar cada palavra inteira como um bloco único, o método quebra o texto em pedaços menores (subpalavras), como se fosse quebrar uma frase em sílabas ou raízes de palavras.

Analogia: Em vez de tentar empilhar 100 caixas de sapatos inteiras, você desmonta algumas e empilha apenas os "pares de sapatos" e "meias" separadamente. Isso ajuda a lidar com palavras estranhas ou que não existem no dicionário padrão.

Passo B: A "Lista de Prioridade" (Ordenação por Frequência)

Aqui está a mágica. O computador conta quantas vezes cada "bloco" aparece.

Os blocos mais comuns (que aparecem milhões de vezes) recebem números pequenos (0, 1, 2, 3...).
Os blocos raros recebem números grandes.
Analogia: Imagine que você vai para uma festa. Em vez de dar um crachá com um número aleatório para cada pessoa, você dá crachás com números baixos (1, 2, 3) para os convidados mais famosos e frequentes, e números altos para os que aparecem só uma vez.

Passo C: O "Envelope Mágico" (Codificação Varint)

Agora, como os números mais comuns são pequenos, eles ocupam menos espaço no envelope!

Um número pequeno (como 5) cabe em um único byte (um "pedaço" de informação).
Um número grande precisa de vários bytes.
Analogia: Como a maioria das pessoas na festa tem crachá pequeno (1, 2, 3), você consegue escrever o nome de todos em um único post-it. Se todos tivessem crachás gigantes, você precisaria de um rolo de papel higiênico inteiro só para anotar os nomes.

3. O Resultado: Por que isso funciona tão bem?

Depois de fazer essa reorganização, o texto se transforma em uma sequência de números onde a maioria é muito pequena e repetitiva.

Quando você joga esse texto reorganizado dentro de um compressor tradicional (como o zlib ou LZMA, que são como "máquinas de espremer" de arquivos), elas funcionam muito melhor.

Por que? Porque essas máquinas são ótimas em encontrar padrões repetidos. Ao reorganizar o texto, você criou um padrão gigante de "pequenos números repetidos", que a máquina espreme com facilidade.

4. A Surpresa: É Mais Rápido!

O artigo descobriu algo incrível: para os compressores mais lentos e pesados (que levam muito tempo para espremer os arquivos), esse método não só deixa o arquivo menor, mas também acelera o processo.

Analogia: É como se, ao reorganizar a bagagem antes de colocar no caminhão, o motorista pudesse dirigir mais rápido porque a carga estava mais leve e organizada. O tempo gasto para reorganizar é compensado pelo tempo ganho no transporte.

5. Quem ganha e quem perde?

Ganham muito: Compressores simples e rápidos (como o zlib). Eles ganham até 7% a mais de eficiência, o que é enorme em escala de internet.
Ganham pouco: Compressores super complexos que já tentam adivinhar padrões sozinhos. Eles já são tão inteligentes que a reorganização ajuda menos, mas ainda ajuda.
Não funciona: Para dados que não são texto (como arquivos de vídeo já comprimidos ou criptografados), pois eles não seguem a "Lei de Zipf" (não têm palavras frequentes).

Resumo Final

Imagine que você tem um texto bagunçado. O método pega esse texto, troca as palavras frequentes por números curtos e simples, e entrega para o compressor. O compressor, ao ver tantos números curtos e iguais, consegue espremer o arquivo como se fosse uma esponja seca, deixando-o muito menor e, em alguns casos, fazendo isso mais rápido.

É uma técnica simples (pode ser feita com menos de 50 linhas de código), mas que economiza milhões de gigabytes de espaço na internet, sem precisar de inteligência artificial complexa.

1. Problema e Motivação

A compressão de texto sem perdas é fundamental para a computação moderna. Os compressores práticos baseados em dicionário (família LZ77, como zlib, zstd, LZMA) funcionam explorando padrões repetidos de bytes através de referências de volta em uma janela deslizante. No entanto, eles não modelam explicitamente as frequências dos símbolos.

O artigo identifica que a linguagem natural segue a Lei de Zipf, uma distribuição de lei de potência onde uma pequena fração de tokens (palavras ou subpalavras) ocorre com muita frequência, enquanto a maioria ocorre raramente. Os compressores padrão não aproveitam totalmente essa concentração de probabilidade, pois os identificadores (IDs) dos tokens são atribuídos arbitrariamente durante o treinamento, resultando em uma distribuição de bytes menos otimizada para a compressão subsequente.

2. Metodologia: Tokenização Ordenada por Frequência

O autor propõe uma etapa de pré-processamento simples, baseada em três passos principais, que transforma o texto em uma representação mais amigável para compressores da família LZ:

Tokenização BPE (Byte Pair Encoding): O texto é tokenizado usando BPE (padrão em modelos de linguagem grandes), que opera no nível de subpalavras. Isso lida com variação morfológica, tokens fora do vocabulário e scripts não latinos (como Chinês e Árabe) sem regras específicas de idioma.
Reordenação de Frequência: O vocabulário do tokenizador é reordenado. Os tokens mais frequentes recebem os menores identificadores inteiros (IDs), e os menos frequentes recebem IDs maiores.
Codificação de Inteiros Variáveis (Varint): Os IDs reordenados são codificados usando o formato LEB128 (Little Endian Base 128). Neste esquema:
- IDs de 0 a 127 ocupam apenas 1 byte.
- IDs de 128 a 16.383 ocupam 2 bytes.
- IDs maiores ocupam 3 ou mais bytes.

Resultado do Pré-processamento: Devido à Lei de Zipf, a grande maioria dos tokens frequentes agora possui IDs pequenos, o que significa que a maior parte do fluxo de dados de entrada para o compressor consiste em bytes únicos (0-127). Isso cria padrões de bytes altamente repetitivos que os algoritmos LZ (como zlib e zstd) conseguem comprimir com extrema eficiência.

O pipeline completo pode ser implementado em menos de 50 linhas de código e não requer redes neurais ou parâmetros aprendidos além do vocabulário do tokenizador.

3. Contribuições Principais

Melhoria de Taxa de Compressão: A técnica aumenta a eficiência de compressão em 1 a 7 pontos percentuais (pp) em compressores LZ, superando transformações clássicas como a Word Replacing Transform (WRT).
Aceleração de Compressão: Para algoritmos computacionalmente caros (como zstd-22 e LZMA), o pré-processamento resulta em uma melhoria de Pareto: melhora tanto a taxa de compressão quanto a velocidade total. O fluxo de entrada menor e mais simples reduz o tempo de busca de correspondências (match-finding).
Análise Teórica e Empírica: O trabalho fornece uma análise teórica baseada na Lei de Zipf (com expoente $\alpha \approx 1.04$ ) e valida a eficácia em múltiplos idiomas (Inglês, Chinês, Árabe) e escalas de arquivo (de 100 KB a 1 GB).

4. Resultados Experimentais

Os testes foram realizados no benchmark padrão enwik8 (100 MB do Wikipedia) e enwik9 (1 GB).

Desempenho de Compressão (enwik8):
- zlib-9: Melhoria de 7,08 pp (redução de 36,48% para 29,40% do tamanho original).
- LZMA: Melhoria de 1,69 pp.
- zstd-22: Melhoria de 0,76 pp.
- Nota: Compressores estatísticos avançados (como PPMd) ou baseados em BWT (bz2) não se beneficiaram ou pioraram ligeiramente, pois já modelam a estrutura de frequência ou contexto internamente.
Velocidade (Trade-off Velocidade-Razão):
- Para o zstd-22, o tempo total de compressão caiu de 95,5s para 30,5s (aceleração de 3,1x), apesar do custo de pré-processamento (~12s).
- Para o LZMA, o tempo caiu de 89,8s para 37,6s (aceleração de 2,4x).
- Isso ocorre porque o fluxo de entrada pré-processado é significativamente menor (41,6 MB vs 100 MB) e possui estrutura estatística mais simples.
Generalização:
- A técnica funcionou consistentemente em textos em Chinês e Árabe, demonstrando que o BPE lida bem com scripts não latinos.
- Funcionou em diferentes tamanhos de arquivo, com ganhos relativamente maiores em arquivos menores (onde o compressor tem menos dados para aprender padrões).
Comparação com WRT (Word Replacing Transform):
- A abordagem baseada em BPE superou a WRT clássica. Enquanto a WRT substitui palavras inteiras, o BPE lida com subpalavras, resultando em um vocabulário menor e mais compacto, evitando a necessidade de entradas separadas para cada forma superficial de uma palavra.

5. Significado e Limitações

Significado: O trabalho demonstra que uma simples reordenação de tokens baseada em frequência pode fechar a lacuna entre compressores práticos rápidos (LZ) e métodos estatísticos mais complexos, sem alterar os algoritmos de compressão existentes. É uma solução "plug-and-play" que oferece ganhos substanciais em escala (web, IA conversacional, pipelines de dados).
Limitações:
- Custo de Overhead: O mapeamento de frequência (vocabulário) deve ser armazenado junto com os dados comprimidos (0,2% do tamanho original no enwik8).
- Velocidade de Descompressão: A descompressão atual é mais lenta devido à decodificação de varint e remapeamento (especialmente em implementações Python não otimizadas), tornando-a mais adequada para cargas de trabalho de arquivamento (escrita pesada) do que para streaming sensível à latência.
- Especificidade de Domínio: Funciona apenas para dados com estatísticas de Lei de Zipf (texto natural). Dados binários, criptografados ou já comprimidos não se beneficiam.
- Requisito de Duas Passadas: Requer uma passagem completa sobre os dados para contar frequências antes da compressão, incompatível com compressão de streaming em uma única passada.

Conclusão

O artigo apresenta uma técnica elegante e teoricamente fundamentada que explora a Lei de Zipf para otimizar a entrada de compressores LZ. Ao transformar tokens frequentes em bytes únicos repetitivos, a "Tokenização Ordenada por Frequência" oferece ganhos significativos de taxa de compressão e, crucialmente, acelera compressores caros, estabelecendo um novo padrão de eficiência para o processamento de grandes volumes de texto.