Índice:
- Definição - O que significa Burrows-Wheeler Transform (BWT)?
- Techopedia explica Burrows-Wheeler Transform (BWT)
Definição - O que significa Burrows-Wheeler Transform (BWT)?
A transformação Burrows-Wheeler (BWT) é um algoritmo que pega blocos de dados, como seqüências de caracteres, e os reorganiza em execuções de caracteres semelhantes. Após a transformação, o bloco de saída contém os mesmos elementos de dados exatos antes de iniciar, mas difere na ordem. A natureza do algoritmo tende a colocar caracteres semelhantes próximos um do outro, facilitando a compactação da ordem de dados resultante. Por isso, é usado em muitos algoritmos de compactação.
Techopedia explica Burrows-Wheeler Transform (BWT)
O algoritmo de transformação 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 "Um algoritmo de compactação de dados sem perda de classificação de blocos".
No mais básico, o BWT pega um bloco de dados como uma string, adicionando um caractere EOF e depois classificando todas as rotações dessa string em ordem lexicográfica. O seguinte pseudocódigo ou etapas ilustram o algoritmo:
- Crie uma tabela que contenha linhas que representem todas as rotações possíveis de um incremento da sequência.
- Classifique todas as linhas em ordem alfabética.
- Saída a última coluna da tabela.
Por exemplo: a palavra "banana"; adicionar um caractere EOF o transforma em "banana $" e aplicamos o algoritmo:
1. Crie uma tabela com linhas representando todas as rotações possíveis:
banana $
anana $ b
nana $ ba
ana $ ban
na $ bana
a $ banan
$ banana
2. Classifique as linhas alfabeticamente / lexicograficamente com base na primeira coluna:
$ banana
a $ banan
ana $ ban
anana $ b
banana $
nana $ ba
na $ bana
3.Retorne a última coluna como a saída BWT: annb $ aa
A sequência resultante é mais fácil de compactar porque caracteres repetidos são agrupados um ao lado do outro. Mas é preciso haver dados adicionais armazenados com os dados transformados para que uma transformação reversa possa ser feita. Embora os dados transformados resultantes sejam maiores que sua forma original, mas sua característica de compressibilidade seja aumentada muitas vezes, tornando-o essencialmente um método "livre" para melhorar a eficiência dos métodos de compressão.
