Efficient Grammar Compression via RLZ-based RePair

O artigo apresenta o RLZ-RePair, um algoritmo que gera gramáticas RePair exatas a partir de uma análise RLZ, reduzindo significativamente o uso de memória em comparação com o método RePair tradicional enquanto mantém a qualidade da compressão.

O essencial

Imagine que você tem um livro gigante, cheio de repetições, como um manual de instruções onde a mesma frase aparece milhares de vezes. O objetivo é encolher esse livro para caber em um pequeno cartão de memória, sem perder nenhuma palavra.

Aqui está a explicação do artigo, traduzida para uma linguagem simples e cheia de analogias:

O Problema: O "RePair" e a Memória Cheia

Existe um método antigo e muito inteligente chamado RePair para comprimir textos. Pense nele como um editor de texto super-rápido que diz: "Olha, a palavra 'abacaxi' aparece 1.000 vezes. Vamos criar uma sigla 'A' para ela. Agora, onde aparece 'A' + 'bola', vamos criar a sigla 'B'." Ele faz isso repetidamente, criando uma estrutura hierárquica (uma gramática) que representa o texto inteiro de forma muito compacta.

O problema: Para fazer isso, o RePair tradicional precisa ler todo o livro de uma vez e colocá-lo na memória do computador (RAM). Se o livro for gigante (como o genoma de um vírus ou de um humano), o computador "explode" de memória e trava. É como tentar guardar uma floresta inteira dentro de uma caixa de sapatos.

A Solução Antiga (e Imperfeita): O "Corte e Cola"

Outros métodos tentaram resolver isso cortando o texto em pedaços menores (como usar um rsync, que é uma ferramenta para sincronizar arquivos) e comprimir cada pedaço separadamente.

• A analogia: Imagine que você tem um quebra-cabeça gigante. Em vez de tentar ver o quadro todo, você corta o quebra-cabeça em 100 pedaços e tenta encaixar as peças de cada pedaço separadamente.
• O defeito: Isso funciona rápido e usa pouca memória, mas você perde a visão do "quadro todo". Você pode cortar uma peça importante ao meio, e o padrão que existia entre duas peças vizinhas se perde. O resultado final não é tão elegante ou eficiente quanto o original.

A Nova Solução: O "RLZ-RePair" (O Detetive Inteligente)

Os autores deste artigo criaram uma nova técnica chamada RLZ-RePair. Eles combinaram a inteligência do RePair com uma técnica chamada RLZ (Relative Lempel-Ziv).

Como funciona a mágica?

1. A Referência (O Mapa): Em vez de olhar para o livro gigante inteiro, o algoritmo escolhe um "livro de referência" (uma amostra pequena que representa bem o todo). Pense nisso como um mapa de metrô. Você não precisa desenhar cada trilho da cidade inteira; você só precisa de um mapa que mostre as linhas principais.
2. O Parse (O Roteiro): O texto gigante é dividido em frases que dizem: "Essa parte aqui é igual à parte X do mapa" ou "Essa parte é igual à parte Y do mapa". Se uma parte não estiver no mapa, ela é escrita como um "literal" (uma letra nova).
3. A Compressão (O Editor): Agora, em vez de tentar comprimir o livro gigante inteiro na memória, o algoritmo foca apenas no Mapa (Referência) e no Roteiro (lista de referências).
   • Ele procura os padrões mais frequentes dentro do mapa.
   • Como o mapa é pequeno, ele cabe facilmente na memória.
   • Quando ele substitui um padrão no mapa (ex: transforma "AA" em "4"), essa mudança se propaga automaticamente para todas as vezes que aquele padrão foi citado no roteiro.

A Analogia do "Código de Barras":
Imagine que o texto gigante é um supermercado cheio de produtos.

• O RePair antigo tenta colocar um código de barras em cada item individualmente, mas precisa ver todos os produtos ao mesmo tempo para encontrar os pares mais comuns. O estoque fica lotado.
• O RLZ-RePair pega um único "catálogo de referência" (o mapa). Ele diz: "Todo o corredor de bebidas é igual ao corredor 5 do catálogo". Ele então otimiza o catálogo. Como o catálogo é pequeno, ele consegue ver todos os padrões ali. Quando ele muda algo no catálogo, automaticamente todos os corredores que apontam para ele são atualizados.

Por que isso é incrível?

1. Economia de Memória: O artigo mostra que essa técnica usa mais de 80% menos memória do que o RePair tradicional. É como conseguir organizar a biblioteca inteira usando apenas a estante de referência, sem precisar de um armazém gigante.
2. Qualidade Perfeita: Diferente dos métodos de "corte e cola" (BigRePair, Re2Pair), o RLZ-RePair não perde a estrutura. Ele produz exatamente o mesmo resultado final (a mesma gramática compacta) que o RePair original faria, se tivesse memória suficiente.
3. Velocidade: Ele é um pouco mais lento que os métodos "baratos" (que cortam o texto), mas muito mais rápido do que tentar rodar o RePair original em textos gigantes (que muitas vezes nem consegue rodar).

O Resultado Prático

Os autores testaram isso com dados reais:

• 400.000 genomas do Coronavírus: O método conseguiu comprimir tudo usando apenas 17 GB de memória, enquanto o método antigo precisava de quase 100 GB (e travava).
• Cromossomo Humano 19: O método antigo nem conseguiu terminar a tarefa. O novo método fez o trabalho usando menos da metade da memória disponível no servidor.

Resumo final:
O RLZ-RePair é como um tradutor inteligente que não precisa ler o livro inteiro de uma vez para entendê-lo. Ele usa um "resumo" (a referência) para entender os padrões e, ao melhorar o resumo, melhora automaticamente a compreensão de todo o texto gigante, economizando espaço e tempo sem perder a precisão. É uma solução elegante para um problema que parecia exigir "memória infinita".

Resumo técnico

Título: Compressão de Gramática Eficiente via RePair Baseado em RLZ

1. O Problema

A compressão baseada em gramáticas, especificamente o algoritmo RePair, é conhecida por sua simplicidade e propriedades combinatórias poderosas, gerando gramáticas compactas ao substituir repetidamente os pares de símbolos adjacentes (bigramas) mais frequentes. No entanto, o RePair padrão possui uma limitação crítica: o uso de memória escala mal com o tamanho da entrada, pois exige carregar todo o texto na memória para contar as frequências dos bigramas. Isso torna-o impraticável para conjuntos de dados massivos e altamente repetitivos (como genomas).

Alternativas existentes, como BigRePair e Re2Pair, tentam resolver o problema de escalabilidade utilizando parseamento prévio (como rsync ou parseamento recursivo livre de prefixos). Embora essas abordagens reduzam o uso de memória, elas falham em recuperar a estrutura hierárquica exata do RePair tradicional. Ao dividir a entrada em frases arbitrárias antes da compressão, elas impedem que o algoritmo detecte bigramas frequentes que cruzam os limites dessas frases, resultando em gramáticas com mais regras e menor fidelidade estrutural.

2. Metodologia: RLZ-RePair

Os autores propõem o RLZ-RePair, um algoritmo híbrido que combina a escalabilidade do parseamento RLZ (Relative Lempel-Ziv) com a precisão estrutural do RePair.

• Conceito Central: O algoritmo realiza o parseamento do texto de entrada ($T$) em relação a uma string de referência ($R$) usando RLZ. Isso gera uma sequência de frases onde cada frase corresponde ao prefixo mais longo do restante de $T$ que coincide com uma substring de $R$.
• Mecanismo de Funcionamento:
  1. Parseamento RLZ: O texto é dividido em frases (intervalos) que referenciam posições na string de referência.
  2. Cálculo de Frequências: As frequências dos bigramas são calculadas sobre as frases RLZ, incluindo bigramas que ocorrem inteiramente dentro de uma frase e aqueles que cruzam os limites entre frases.
  3. Substituição Inteligente: O algoritmo seleciona o bigram mais frequente para substituição por um não-terminal.
     • Dentro das Frases: Se o bigram ocorre dentro de uma frase não-explicíta (que referencia a $R$), a substituição é feita apenas na string de referência $R$. Como as frases referenciam $R$, a mudança se propaga automaticamente para todas as ocorrências, sem necessidade de processar o texto completo.
     • Limites de Frase (Boundary Conditions): Se o bigram cruza o limite de uma frase ou se a substituição invalidaria os intervalos das frases (devido a caracteres nas bordas sendo removidos), o algoritmo converte os caracteres afetados em "frases explícitas" (literals) temporárias para preservar a integridade dos intervalos de referência.
  4. Estrutura de Dados: Utiliza uma lista duplamente encadeada embutida em um array para representar $R$ (permitindo acesso aleatório e atualizações de ponteiros sem alterar os índices lógicos das frases), um heap máximo para frequências e árvores de intervalo para gerenciar as frases.

3. Contribuições Chave

• Fidelidade Estrutural Exata: Ao contrário de BigRePair e Re2Pair, o RLZ-RePair produz uma gramática exatamente equivalente à gerada pelo RePair padrão (assumindo uma referência bem escolhida), preservando as propriedades teóricas e a estrutura hierárquica original.
• Redução Drástica de Memória: O método evita carregar o texto completo na memória. O uso de memória é próximo ao tamanho da string de referência, permitindo a compressão de conjuntos de dados que seriam impossíveis de processar com o RePair padrão.
• Eficiência em Substituições: Ao aproveitar a repetitividade capturada pelo RLZ, o número de substituições de bigramas necessárias é significativamente reduzido, pois uma única substituição na referência afeta múltiplas ocorrências no texto.

4. Resultados Experimentais

Os autores avaliaram o RLZ-RePair em dois conjuntos de dados biológicos massivos: 400.000 genomas de SARS-CoV-2 e 1.024 assembleias do cromossomo 19 humano.

• SARS-CoV-2 (400k genomas, ~12 GB):
  • O RLZ-RePair (configuração 0.5%) reduziu o uso de memória em 82,8% (de ~100 GB para ~17 GB) em comparação com o RePair padrão.
  • O tempo de execução aumentou apenas modestamente (27,5% mais lento).
  • O tamanho da gramática comprimida e o número de regras foram idênticos aos do RePair padrão, enquanto BigRePair e Re2Pair geraram gramáticas 20% a 70% maiores.
• Cromossomo 19 (1.024 assembleias, ~60 GB):
  • O RePair padrão falhou em processar o conjunto completo (excedeu 100 GB de RAM e o limite de tempo).
  • O RLZ-RePair conseguiu comprimir o conjunto completo usando entre 31 GB e 41 GB de memória.
  • Ao comparar no maior subconjunto possível para o RePair (256 sequências), o RLZ-RePair usou 83,1% menos memória com um aumento de 34,5% no tempo.
  • Novamente, a qualidade da compressão (tamanho do arquivo e número de regras) foi superior ou igual ao RePair e significativamente melhor que as alternativas escaláveis (BigRePair/Re2Pair).

5. Significância

O RLZ-RePair representa um avanço significativo na compressão de dados repetitivos em grande escala. Ele resolve o dilema histórico entre escalabilidade (memória) e fidelidade estrutural (qualidade da gramática).

• Praticidade: Torna viável a aplicação de compressão baseada em gramáticas (útil para indexação, acesso aleatório e descoberta de padrões) em dados genômicos massivos que antes eram intratáveis.
• Teoria: Demonstra que é possível obter as garantias teóricas do RePair (como gramáticas ótimas para certas classes de strings) sem o custo proibitivo de memória, superando as limitações de métodos de pré-processamento que distorcem a estrutura dos dados.

Em resumo, o RLZ-RePair oferece uma solução prática e teoricamente sólida para a compressão de grandes volumes de dados repetitivos, mantendo a elegância e a eficiência da compressão baseada em gramáticas.