LZ77: diferenças entre revisões

 

O algoritmo LZ77 se baseia na utilização das partes que já foram lidas de de um [[arquivo]] como um dicionário, substituindo as próximas ocorrências das mesmas seqüências de [[caracteres]] pela posição (absoluta ou relativa) da sua última ocorrência. Para limitar o espaço de busca e de [[endereço|endereçamento]] necessário, as ocorrências anteriores são limitadas por uma "janela deslizante" (do inglês ''sliding window'') que tem tamanho fixo e "desliza" sobre o arquivo, delimitando o início e fim da área onde serão buscadas as ocorrências anteriores. O tamanho desta janela é um dos fatores primordiais para se ajustar a performance desse algoritmo.

 

== Algoritmo ==

O [[algoritmo]] LZ77 é relativamente simples. Define-se inicialmente duas estruturas que serão usadas: A ''janela'' de procura, e o ''buffer'' de ''look-ahead'' (num tradução livre poderia ser chamado de ''buffer'' de pré-visualização). A janela representa as partes do [[arquivo]] que já foram lidos, enquanto o ''look-ahead'' representa o que ainda será lido e processado pelo algoritmo. Na prática, o ''look-ahead'' é preenchido de antemão com os próximos [[byte]]s a serem processados pelo compressor. A janela tem tamanho definido, e deve permitir que os dados sejam [[fila|enfileirados]] dentro dela, eliminando os bytes mais antigos quando seu limite de tamanho é atingido. O ''buffer'' de ''look-ahead'' também tem tamanho definido, em geral dezenas de vezes menor que a ''janela''.

 

 

== Exemplo ==

Abaixo ilustramos o [[algoritmo]] LZ77 com um exemplo da compressão da cadeia <code>A_ASA_DA_CASA</code>, usando janela de tamanho 8 e ''buffer'' de ''look-ahead'' de tamanho 4.

 

== Aplicações ==

Alguns programas e formatos de compressão de dados largamente utilizados usam este algoritmo, pois ao contrário do [[LZ78]] e do [[LZW]], seus parentes mais próximos, ele não estava coberto por patentes. A variante mais comum do LZ77 é conhecida como [[DEFLATE]] e combina o uso de LZ77 com o uso de [[Codificação de Huffman|Código Huffman]]. Entre os programas e formatos que usam LZ77 e [[DEFLATE]] temos:

 

== Exemplo de implementação ==

<source lang="python">

# coding: utf-8

 

buffer = str[i:i+self.buffer_size]

tuple = (0, 0, str[i])

for size in range(len(buffer), 0, -1):

index = window.rfind(buffer[0:size])

if index >= 0:

literal = '' # a string vazia representa

if i + size < len(str):

literal = str[i+size]

print decoded

</source>

 

 

== {{Ver também}} ==

 

{{esboço-prog}}