Lz77

Lz77
A codificação consiste em:
•  Ler para uma janela de tamanho predefinido uma sequência de dados a comprimir
•  Dividindo a janela em duas partes, buffer de histórico buffer de dados a codificar,
procurar no buffer de histórico, da direita para a esquerda, a maior sequência de símbolos
igual à sequência de símbolos no buffer de dados a codificar, que começa no primeiro
símbolo.
•  Inicialmente apenas o buffer de dados a comprimir irá ser preenchido com o fluxo de
dados original
•  A distância do ponteiro que aponta para o início dasequência de símbolos igual até ao
início do buffer de dados a codificar chama-se de deslocamento (offset)
•  O número de símbolos iguais (no buffer de histórico buffer de dados a codificar) chamase de comprimento (length)
•  Uma vez encontrada a sequência com maior numero de símbolos iguais, o codificador gera
um código triplo, (o, l, c), onde oé o deslocamento (offset), lé o comprimento (length) e c
(codeword) é símbolo que sucede a sequência de símbolos iguais. A razão para o envio do
terceiro elemento cé para o caso de não ser encontrada nenhuma sequência de símbolos
igual no buffer de histórico
•  Deslocar a janela no fluxo de dados com um deslocamento igual à quantidade de símbolos
codificados no passo anterior (l+ 1)
Algoritmo de codificação:
Carregar dados para o buffer (janela)
Enquanto (buffer de dados a codificar não está vazio)
Obter referência da sequência igual mais longa (o, l)
Se comprimento > 0
Ouput (deslocamento, comprimento, próximo símbolo)
Senão
Outout (0, 0, primeiro símbolo no buffer de dados a codificar)
Deslocar a janela (l+ 1) posições

Anúncios