Método de Burrows-Wheeler

De GirinoWiki

O Método de Burrows-Wheeler é 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 par a 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.

[editar] Histórico

Michael Burrows e David Wheeler publicaram em 1994 um artigo discutindo um trabalho que eles tinham feito no Digital Systems Research Center em Palo Alto na Califórnia. O artigo, "A Block-sorting Lossless Data Compression Algorithm" apresentou um algoritmo de compressão de dados baseado num trabalho anterior não-publicado sobre uma transformada descoberta por Wheeler em 1983^[1].

[editar] Funcionamento

A teoria por traz do método de Burrows-Wheeler é que dado um símbolo presente no bloco de dados, existe uma probabilidade grande deste simbolo 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 sequência de caracteres L que satisfaça as seguintes condições^[2]:

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.
É 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:

swiss_miss
wiss_misss
iss_misssw
ss_missswi
s_missswis
_missswiss
missswiss_
issswiss_m
ssswiss_mi
sswiss_mis

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

0: _missswiss 
1: iss_misssw
2: issswiss_m
3: missswiss_
4: s_missswis
5: ss_missswi
6: ssswiss_mi
7: sswiss_mis 
8: swiss_miss <- linha original
9: wiss_misss

Desta nova matriz podemos preencher as condições dadas mais acima com apenas 2 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 8 pois iniciamos a contagem em 0). Podemos ver que na última coluna desta nova matriz as letras "i" e "s" 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 = "swm_siisss" e o nímero I = 8

[editar] Operação reversa

Reconstruir a primeira coluna da matriz ordenada a partir dos dados comprimidos (a útlima coluna e o número da linha original) é um processo fácil: basta reordenar a linha L que acabamos de descomprimir, obtendo assim "_iimsssssw". 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 "s" se encontra na posição 4 da cadeia ordenada, a segunda letra, o "w", se encontra na posição 9 da cadeia ordenada, e assim por diante, obtendo-se então o vetor T = (4,9,3,0,5,1,2,6,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] \gets L[T^i[I]],$ para $i = 0,1,..., n - 1$ onde $T 0 [j] = j,$ e $T i + 1 [j] = T [T i [j]].$

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

$i = 0 \Rightarrow S[10-1-0] = L[T^0[I]]=L[T^0[8]] = L[8] = \mbox{s},$
$i = 1 \Rightarrow S[10-1-1] = L[T^1[I]]=L[T[T^0[I]]] = L[T[8]] = L[7] = \mbox{s}...$

[editar] Exemplo de implementação

#!/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
        http://pt.wikipedia.org/wiki/Método_de_Burrows-Wheeler
    """
    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" coresponde simplesmente a se
            selecionar a última coluna da matriz de 
            permutações ordenadas lexicograficamente, 
            além de informa 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)

[editar] Referências

↑ M. Burrows; D.J. Wheeler (May 10, 1994). "A block-sorting lossless data compression algorithm" (ps). Technical report, Palo Alto, California: 18. Retirado em 25/06/2007.
↑ SALOMON, David. Data Compression: The Complete Reference. 2.ed. Nova Iorque: Springer, 2000. ISBN 0-387-95045-1 página 682.

Retirado de "http://www.girino.org/girinowiki/M%C3%A9todo_de_Burrows-Wheeler"

Categorias: Computação | Compressão de dados