Método de Burrows-Wheeler
O Método de Burrows-Wheeler, também conhecido pela sigla em inglês BWT, é um processamento estatístico de um bloco de dados que aumenta a redundância espacial, facilitando a aplicação de técnicas de compressão de dados.
A teoria por trás do método de Burrows-Wheeler é que, dado um símbolo presente no bloco de dados, há uma grande probabilidade desse símbolo ser sempre precedido do mesmo conjunto de símbolos. Por exemplo, na língua inglesa: a letra "H" tem maior probabilidade de ser precedida pela letra "T" do que por qualquer outra letra. Usando este princípio, o método tenta construir uma seqüência de caracteres L que satisfaça as seguintes condições: A forma como o método de Burrows-Wheeler atinge este objetivo é a seguinte: em primeiro lugar, constrói-se uma matriz n x n onde n é o tamanho do bloco a ser comprimido. Esta matriz é preenchida na primeira linha com o bloco original; na segunda linha com o bloco rotacionado a esquerda de uma posição; na terceira linha com o bloco rotacionado de 2 posições, e assim por diante, até termos na última linha o bloco rotacionado de n-1 posições. O exemplo abaixo demonstra o processo:
Operação reversa
Reconstruir a primeira coluna da matriz ordenada a partir dos dados comprimidos (a última coluna e o número da linha original) é um processo fácil: basta reordenar a linha L que acabamos de descomprimir, obtendo assim "___aaaaaacdss". Durante este processo de reordenação, construímos um novo vetor que mapeia as posições da letra na L antiga para a sua respectiva posição na cadeia ordenada. Por exemplo, a primeira posição da cadeia, letra "a" se encontra na posição 3 da cadeia ordenada, a segunda letra "a" se encontra na posição 4 da cadeia ordenada, e assim por diante, obtendo-se então o vetor T = (3,4,5,6,10,11,12,0,9,1,2,7,8). Com este vetor T e o valor I armazenado junto com a cadeia comprimida podemos então reconstruir a cadeia original S pela seguinte fórmula: S [ n − 1 − i ] ← L [ T i [ I ] ] , {\displaystyle S[n-1-i]\gets L[T^{i}[I]],} para i = 0 , 1 , . . . , n − 1 {\displaystyle i=0,1,...,n-1} onde T 0 [ j ] = j , {\displaystyle T^{0}[j]=j,} e T i + 1 [ j ] = T [ T i [ j ] ] . {\displaystyle T^{i+1}[j]=T[T^{i}[j]].}
O método de Burrows-Wheeler foi difundido principalmente pelo utilitário de compactação de dados bzip2.
