Método de Burrows-Wheeler

Esta página cita fontes, mas que não cobrem todo o conteúdo. Ajude a inserir referências. Conteúdo não verificável pode ser removido.—Encontre fontes: ABW  • CAPES  • Google (N • L • A) (Novembro de 2015)

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.

Diferentemente de outras técnicas usadas para compressão de dados que trabalham com um fluxo contínuo de bytes tratados um a um, o método de Burrows-Wheeler trabalha com blocos geralmente grandes de dados que são processados em conjunto antes de serem comprimidos.

Funcionamento[editar | editar código-fonte]

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:^[1]

1. Qualquer região de L tende a apresentar uma concentração de apenas poucos símbolos. Isso permite que L seja facilmente comprimido por técnicas de move-to-front e RLE.
2. É possível reconstruir o bloco de dados original com pouca ou nenhuma informação adicional.

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:

a_asa_da_casa _asa_da_casaa asa_da_casaa_ sa_da_casaa_a a_da_casaa_as _da_casaa_asa da_casaa_asa_ a_casaa_asa_d _casaa_asa_da casaa_asa_da_ asaa_asa_da_c saa_asa_da_ca aa_asa_da_cas 

O segundo passo é agora reordenar esta matriz em ordem lexicográfica, obtendo então a seguinte matriz:

 0: _asa_da_casaa  1: _casaa_asa_da  2: _da_casaa_asa  3: a_asa_da_casa <- linha original  4: a_casaa_asa_d  5: a_da_casaa_as  6: aa_asa_da_cas  7: asa_da_casaa_  8: asaa_asa_da_c  9: casaa_asa_da_ 10: da_casaa_asa_ 11: sa_da_casaa_a 12: saa_asa_da_ca 

Desta nova matriz podemos preencher as condições dadas mais acima com apenas duas informações: a última coluna, que preenche a condição 1, e o número I da linha que corresponde ao bloco original (neste caso, a linha 3, pois iniciamos a contagem em 0). Podemos ver que na última coluna desta nova matriz os simbolos "a" e "_" se acumularam em uma parte específica da matriz. Em um bloco de tamanho maior, este efeito é ainda mais acentuado, melhorando ainda mais a eficiência dos métodos de compressão.

Os dados que precisamos comprimir então são a linha L = "aaaadss_c__aa" e o número I = 3

Operação reversa[editar | editar código-fonte]

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: ${\displaystyle S[n-1-i]\gets L[T^{i}[I]],}$ para ${\displaystyle i=0,1,...,n-1}$ onde ${\displaystyle T^{0}[j]=j,}$ e ${\displaystyle T^{i+1}[j]=T[T^{i}[j]].}$

A reconstrução dos primeiros elementos da cadeia original fica então sendo:

${\displaystyle i=0\Rightarrow S[13-1-0]=L[T^{0}[I]]=L[T^{0}[3]]=L[3]={\mbox{a}},}$

${\displaystyle i=1\Rightarrow S[13-1-1]=L[T^{1}[I]]=L[T[T^{0}[I]]]=L[T[3]]=L[6]={\mbox{s}}...}$

Aplicações[editar | editar código-fonte]

O método de Burrows-Wheeler foi difundido principalmente pelo utilitário de compactação de dados bzip2.

Exemplo de implementação[editar | editar código-fonte]

# !/usr/bin/python # coding: utf-8  import sys  class bwt_encoder:     """         Transforma um bloco de caracteres em uma seqüência         mais facilmente comprimível usando o método de         Burrows-Wheeler, de acordo com o descrito em      """     def get_permutations(self, str):         """             Cria as permutações de um bloco que são             necessárias ao BWT.         """         ret = []         for i in range(0, len(str)):             ret = ret + [str[i:] + str[0:i]]         return ret     def encode(self, str):         """             A "codificação" corresponde simplesmente a se             selecionar a última coluna da matriz de             permutações ordenadas lexicograficamente,             além de informar a posição da cadeia original             nesta matriz de permutações.         """         perms = self.get_permutations(str)         perms.sort()         last_column = ''         for line in perms:             last_column = last_column + line[len(line)-1]         index = 0         for index in range(0, len(perms)):             if perms[index] == str:                 break         return (index, last_column)  class bwt_decoder:     """         Faz a transformação reversa da         descrita em bwt_encode.     """     def get_indexes(self, str, sorted):         """             Os índices mapeiam cada símbolo da cadeia             "codificada" com os símbolos da cadeia             ordenada. Esta lista de índices é o             elemento essencial na transformação reversa.         """         used_pos = dict()         indexes = []         for i in range(0, len(str)):             for j in range(0, len(sorted)):                 if sorted[j] == str[i] and (not used_pos.has_key(j)):                     used_pos[j] = True                     indexes = indexes + [j]                     break         return indexes     def decode(self, str, index):         """             Usando a lista de índices calculadas no método             get_indexes e o índice correspondentes a linha             original na matriz, reconstruímos a linha             original, que corresponde ao arquivo decodificado.         """         sorted = [str[i] for i in range(0, len(str))]         sorted.sort()         indexes = self.get_indexes(str, sorted)         ret = ''         T = index         for i in range(0, len(str)):             char = str[T]             ret = char + ret             T = indexes[T]         return ret  if __name__ == "__main__":     str = 'a_asa_da_casa'  # encode     encoder = bwt_encoder()     (index, last_column) = encoder.encode(str)     print ('encoded:', index, last_column)  # decode     decoder = bwt_decoder()     decoded = decoder.decode(last_column, index)     print ('decoded:', decoded) 

Referências