LZ77 (python)

De GirinoWiki

#!/usr/bin/python
# coding: utf-8
 
import sys
 
class lz77:
    """
       Esta classe comprime uma sequencia de caracteres usando
       o algorítmo LZ77 como descrito em
       http://pt.wikipedia.org/wiki/LZ77
 
       Esta é uma implementação didática, para exemplificar
       o funcionamento do algoritmo, e não possui nenhum tipo de
       otimização, por isso seu desempenho em situações reais 
       deve ser muito abaixo do esperado.
    """
    def __init__(self, window_size = 65535, buffer_size=255):
        """
           Carrega os parametros de tamanho de janela e buffer 
           de look-ahead
        """
        self.window_size = window_size
        self.buffer_size = buffer_size
    def encode(self, str):
        """
            Aplica o algoritmo LZ77 na cadeia de entrada, gerando
            uma lista de "tuplas" na saída. Cada tupla correpsonde
            a (posição, tamanho, literal) onde posição é a posição
            relativa da cadeia encontrada na janela, tamanho é o 
            tamanho dessa cadeia e literal é o símbolo que segue
            a cadeia nessa sequencia.
        """
        ret = []
        i = 0
        while i < len(str):
            begin_window = i-self.window_size
            if begin_window < 0:
                begin_window = 0
            window = str[begin_window:i]
            buffer = str[i:i+self.buffer_size]
            tuple = (0, 0, str[i])
            # Este "loop" é o "coração" do algoritmo. Aqui procuramos
            # a maior sequencia dentro da janela (window) que case
            # com o início do buffer. A implementação atual simplesmente
            # procura por ocorrências de substrings cada vez menores
            # do buffer até encontrar alguma. Implementações mais
            # eficientes usariam um dicionário de prefixos, uma trie
            # ou uma tabela de espalhamento.
            for size in range(len(buffer), 0, -1):
                index = window.rfind(buffer[0:size])
                if index >= 0:
                    literal = '' # a string vazia representa 
                                 # o final do arquivo.
                    if i + size < len(str):
                        literal = str[i+size]
                    tuple = (len(window)-index-1, size, literal)
                    break
            i = i + tuple[1] + 1
            ret = ret + [tuple]
        return ret
    def decode(self, list):
        # a decodificação é extremamente simples: basta copiar a
        # subsequÊncia indicada pela tupla para o final da sequencia
        # de saída e acrescentar o novo caractere literal.
        ret = ''
        for tuple in list:
            pos = len(ret) - tuple[0] - 1
            ret = ret + ret[pos:pos+tuple[1]] + tuple[2]
        return ret
 
if __name__ == "__main__":
    str = 'A_ASA_DA_CASA'
    encoder = lz77(8,4)
    encoded = encoder.encode(str)
    print encoded
 
    decoder = lz77(8,4)
    decoded = decoder.decode(encoded)
    print decoded