Definição - O que significa a transformação de Burrows-Wheeler (BWT)?
A transformação Burrows-Wheeler (BWT) é um algoritmo que pega blocos de dados, como strings, e os reorganiza em séries de caracteres semelhantes. Após a transformação, o bloco de saída contém os mesmos elementos de dados exatos antes de ter iniciado, mas difere na ordem. A natureza do algoritmo tende a colocar caracteres semelhantes próximos uns dos outros, tornando a ordem de dados resultante mais fácil de compactar. Por isso, é usado em muitos algoritmos de compressão.
Definirtec explica a transformação de Burrows-Wheeler (BWT)
O algoritmo de transformação de Burrows-Wheeler é um algoritmo relativamente novo inventado em 1994 por Michael Burrows e David Wheeler e baseado em uma transformação não publicada descoberta por Wheeler em 1983, publicada em seu artigo "A Block-sorting Lossless Data Compression Algorithm."
Basicamente, o BWT pega um bloco de dados como uma string, adicionando um caractere EOF e, em seguida, classificando todas as rotações dessa string em ordem lexicográfica. O seguinte pseudocódigo ou etapas ilustram o algoritmo:
- Crie uma tabela que contém linhas que representam todas as rotações de um incremento possíveis da string.
- Classifique todas as linhas em ordem alfabética.
- Produza a última coluna da tabela.
Por exemplo: a palavra “banana”; adicionar um caractere EOF o transforma em “banana $” e então aplicamos o algoritmo:
1. Crie uma tabela com linhas representando todas as rotações possíveis:
banana $
anana $ b
nana $ ba
ana $ ban
na $ eu
uma $ banana
$ banana
2. Classifique as linhas em ordem alfabética / lexicográfica com base na primeira coluna:
$ banana
uma $ banana
ana $ ban
anana $ b
banana $
nana $ ba
na $ eu
3. Retorne a última coluna como a saída BWT: annb $ aa
A string resultante é mais fácil de compactar porque os caracteres repetidos são agrupados lado a lado. Mas é necessário que haja dados adicionais armazenados com os dados transformados para que uma transformação reversa possa ser feita. Mesmo que os dados transformados resultantes sejam maiores do que sua forma original, sua característica de compressibilidade é aumentada muitas vezes, essencialmente tornando-o um método “gratuito” de melhorar a eficiência dos métodos de compressão.