Burrows e Wheeler reordenaram as rotações de um bloco para torná-lo muito mais compressível

A compressão sem perdas é limitada pela quantidade de redundância que um método consegue enxergar. A família LZ e a codificação de Huffman atingem, cada uma, um patamar em texto comum.

O relatório DEC de 1994 de Burrows e Wheeler descreveu uma transformada de ordenação de blocos: listar todas as rotações do bloco, ordená-las e emitir a última coluna. Como as rotações compartilham sufixos, caracteres idênticos se agrupam, e uma breve passagem de run-length e move-to-front transforma isso em pouquíssimos símbolos.

A transformada é invertível, portanto é um rearranjo, não uma perda. O resultado alimentou o bzip2, que comprimia texto com mais eficácia do que ferramentas contemporâneas e tornou a técnica o padrão para compressão lenta, porém justa.

Ordenar as rotações do bloco para que os semelhantes fiquem vizinhos

Ordenar as rotações aproxima símbolos idênticos onde o contexto é o mesmo.

A codificação run-length e move-to-front então encontra sequências longas e baratas.

A transformada é uma permutação, então a descompressão é exata.

Funciona em qualquer estrutura repetida, portanto não é ajustada a um único tipo de arquivo.

Antes de comprimir, reordene os dados para que símbolos idênticos fiquem lado a lado. Uma transformada que agrupa as partes previsíveis pode tornar um compressor comum drasticamente mais forte.

A transformada de Burrows-Wheeler tornou-se o motor do bzip2 e, mais tarde, a base do FM-index, que localiza substrings e mapeia genomas. A mesma ideia impulsiona hoje ferramentas de alinhamento de bioinformática de alto rendimento.