Transformada de Burrows-Wheeler (BWT)

Ao ordenar todas as rotações cíclicas de um texto, cada rotação que compartilha o mesmo sufixo acaba adjacente às demais. A última coluna — o caractere logo antes de cada prefixo ordenado — reúne caracteres que precediam o mesmo contexto no texto original. Padrões repetidos fazem com que muitas rotações compartilhem um sufixo comum, então o mesmo caractere precedente aparece várias vezes seguidas na última coluna. Essas sequências são o que RLE e a codificação move-to-front exploram. A transformação é sem perdas porque a primeira coluna F (BWT ordenada) e a última coluna L (a própria BWT) codificam juntas um mapeamento completo — o mapeamento LF — permitindo reconstruir o original caractere por caractere apenas com essas duas colunas e a chave.

Sozinha, a BWT não deixa o texto menor: a saída tem exatamente o mesmo comprimento e os mesmos caracteres, apenas em outra ordem. Seu verdadeiro papel é ser uma etapa de preparação reversível que agrupa caracteres iguais, para que os compressores seguintes — move-to-front, codificação por comprimento de sequência e depois Huffman ou codificação aritmética — tenham vida fácil. A lição: o ganho não está no tamanho da saída da BWT, mas em quão mais compressível essa saída se torna.

Uma ideia de compressão tornou-se discretamente um pilar da genômica. Envolta numa estrutura chamada índice FM, a BWT permite buscar um fragmento curto de DNA dentro de um genoma humano de 3 bilhões de letras armazenando esse genoma em apenas alguns gigabytes. Alinhadores como Bowtie e BWA — o Burrows-Wheeler Aligner — são construídos sobre ela, de modo que um truque de compressão de 1994 hoje sustenta o pareamento diário de milhões de leituras de sequenciamento.