Transformada de Burrows-Wheeler (BWT)

observe rotações cíclicas sendo ordenadas em uma matriz cuja última coluna agrupa caracteres repetidos - e depois reverta o processo sem perdas

Valores iniciais — Transformada de Burrows-Wheeler (BWT)

Texto de entrada	banana

Altere qualquer controlo acima e os resultados são recalculados.

A carregar a simulação interativa...

por que ordenar rotações cria sequências repetidas 🖖

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.

A BWT reordena, não encolhe 🖖

Por si só, a BWT não reduz o texto: o resultado tem exatamente o mesmo comprimento e os mesmos caracteres, apenas dispostos noutra ordem. A sua verdadeira função é servir de preparação reversível, agrupando caracteres iguais para facilitar o trabalho dos compressores seguintes: transformação move-to-front, codificação por comprimento de sequência e, por fim, codificação de Huffman ou aritmética. Em "abracadabra$", o resultado contém os mesmos doze caracteres, com quatro letras a consecutivas, embora na entrada nunca houvesse duas lado a lado.

O mesmo truque que mapeia seu DNA 🖖

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.

Problema resolvido na íntegra

A transformada de Burrows–Wheeler de "banana$" com todas as sete rotações ordenadas 5 passos
Encontre a transformação de Burrows–Wheeler de "banana$" e decida depois se algo foi comprimido. Este é o passo saída BWT: sentinela acrescentada, todas as sete rotações ordenadas, última coluna lida.
1. A sentinela é acrescentada antes de acontecer qualquer outra coisa. Como o $ se ordena antes de qualquer letra e aparece exatamente uma vez, duas rotações nunca comparam como iguais, pelo que a ordenação tem uma resposta única e não ambígua.
  
  $s = banana$ (n = 7), r_{k} = s [k :] + s [: k], k = 0, \dots, 6$
2. Ordenar lexicograficamente as rotações é o único trabalho realizado pela transformação. Lendo ao longo das sete linhas, note-se que a ordenação agrupou a cadeia pelo que vem depois de cada posição.
  
  $$banana, a$banan, ana$ban, anana$b, banana$, na$bana, nana$ba$
3. O último carater de uma rotação é o carater situado imediatamente antes do seu primeiro carater no original. É por isso que a ordenação produz sequências: as linhas 1 e 2 começam ambas por 'a' e terminam ambas em 'n', porque ambos esses a estão precedidos por um n em banana. A chave é o número da linha do original e, sem ela, a transformação não pode ser invertida.
  
  $L_{j} = s_{(k_{j} - 1) mod n} ⟹ L = annb$aa, key = 4$
4. Nada foi comprimido ainda, nem o poderia ter sido — a saída é uma permutação da entrada, os mesmos sete carateres numa ordem diferente. O que mudou foi a estrutura de sequências, e isso foi a única coisa que mudou.
  
  $b ∣ a ∣ n ∣ a ∣ n ∣ a ∣ $ : R = 7, \overset{r}{ˉ} = 1.00 ⟶ a ∣ nn ∣ b ∣ $ ∣ aa : R = 5, \overset{r}{ˉ} = \frac{7}{5} = 1.4$
5. O RLE cobra dois bytes por sequência, pelo que cinco sequências custam dez bytes face a uma entrada de sete bytes. O seu ponto de equilíbrio nunca muda: o número de sequências tem de ser inferior a metade do comprimento, o que aqui significa três ou menos.
  
  $2 R = 10 > N = 7 ⟹ \frac{7}{10} = 0.70 \times, 2 R < N ⟺ R < 3.5$
Resposta

O painel apresenta annb$aa com key = 4, uma sequência média de 1,4 carateres, 10 bytes de RLE e uma pontuação de 0,70×. A transformação fez exatamente o que promete — elevou a sequência média em 40% sem tocar num único carater — e o pipeline continuou a perder, porque sete carateres não são texto suficiente para que esse ganho cubra dois bytes por sequência. Duplique-se a palavra e a aritmética inverte-se. "bananabanana$" tem treze carateres e a sua transformação é annnnbba$aaaa: seis sequências em vez de cinco, enquanto o comprimento quase duplicou, dando 12 bytes contra 13 e uma pontuação de 1,08×. Esse é todo o argumento a favor da BWT — a contagem de sequências é governada por quantos contextos distintos o texto tem, e não pelo seu comprimento, pelo que quanto mais longo for o bloco, melhor compensa, razão pela qual o bzip2 transforma blocos de até 900 kB em vez de palavras.

$bananabanana$ : N = 13, R = 6 ⟹ 2 R = 12 < 13, \frac{13}{12} = 1.08 \times$

Percurso de aprendizagem

Compressão manual

Referências (3)

Insight blocks 1 and 2 — the transform itself: M. Burrows and D. J. Wheeler, "A Block-sorting Lossless Data Compression Algorithm." Digital Systems Research Center, Research Report 124, 1994.
Insight block 3 — the aligners it turned into: B. Langmead, C. Trapnell, M. Pop and S. L. Salzberg, "Ultrafast and memory-efficient alignment of short DNA sequences to the human genome." Genome Biology 10, R25, 2009.
And the one the block names outright: H. Li and R. Durbin, "Fast and accurate short read alignment with Burrows–Wheeler transform." Bioinformatics 25(14), 1754–1760, 2009.

Pela equipa 42Math · Atualizado 2026-08-17

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Computação →

Problemas de exemplo

banana - "banana$" transforma-se em "annb$aa": as três letras a, antes nunca adjacentes, ficam agora em dois grupos, e o número de sequências desce de 7 para 5.
mississippi - "mississippi$" transforma-se em "ipssm$pissii": é o exemplo clássico e, com este comprimento, o número de sequências mantém-se em 9. A BWT precisa de textos mais longos para que o agrupamento compense.
abracadabra - "abracadabra$" transforma-se em "ard$rcaaaabb": ficam quatro letras a consecutivas, embora no original nunca houvesse duas lado a lado, e o número de sequências desce de 12 para 8. Entre os quatro exemplos disponíveis, este apresenta o melhor agrupamento.
sequência de DNA - "AGATCAGA$" transforma-se em "AGC$GTAAA": três letras A ficam juntas, embora nenhuma fosse adjacente na cadeia original. Num genoma, é este resultado que um índice FM indexa.