Loading AI tools
Da Wikipédia, a enciclopédia livre
LZ78 foi um dos algoritmos de compressão de dados desenvolvidos por Abraham Lempel e Jacob Ziv em 1978, juntamente com o outro algoritmo de compressão LZ77 publicado em 1977. Nos primeiros artigos publicados eles eram conhecidos por LZ1 e LZ2 (LZ77 e LZ78 respectivamente) e só depois ganharam o ano de sua publicação em suas siglas.[1]
O algoritmo LZ78 se baseia na construção de um dicionário com os dados encontrados anteriormente no arquivo a ser comprimido. No início o dicionário se encontra vazio. A medida que o arquivo vai sendo lido, caractere por caractere, cada sequência de caracteres não encontrada no dicionário é introduzida no dicionário e ganha um código. As sequências que já se encontram no dicionário são substituídas pelo seu código no dicionário.
Existem diversas variantes desse algoritmo, entre elas o LZW que se tornou famoso pela facilidade de implementação. Entretanto, várias partes tanto do LZ78 quanto do LZW estavam sujeitas a restrições por patentes, e por isso não puderam se tornar populares durante algum tempo.[1]
O algoritmo LZ78 usa um dicionário (que chamaremos de D) para armazenar as sequências de caracteres encontradas no arquivo, e usa os códigos (posição das sequências no dicionário, ou mesmo um número atribuído sequencialmente às sequências de caracteres encontradas).
Ao ler um caractere do arquivo, procuramos em D para ver se ele já se encontra lá. Caso seja encontrado, lemos o próximo caractere, concatenamos no que já havíamos lido, e procuramos a nova sequência, agora de dois caracteres no dicionário. Enquanto as sequências já estiverem presentes no dicionário, o algoritmo continua lendo e concatenando. Finalmente, quando encontramos um caractere que concatenado à sequência não está presente no dicionário, emitimos na saída um par (Dseq, c) onde Dseq é o código da ultima sequência encontrada no dicionário e c é o caractere que "quebrou" a sequência. Depois de emitir o par na saída, introduzimos a nova sequência terminada em c no dicionário e começamos tudo novamente.
Para que o algoritmo funcione precisamos de inserir inicialmente no dicionário (geralmente sob o código 0) a cadeia vazia (uma entrada no dicionário representando uma cadeia de tamanho zero). Assim, ao ler um caractere c nunca antes lido pelo programa, é emitido na saída o par (0, c).
Um pseudo-código representando este algoritmo está a seguir:
cadeia := '' # inicializa com a cadeia de tamanho 0 D.insere(cadeia) enquanto c := leia_novo_caractere() se D contém cadeia concatenada com c cadeia := cadeia concatenada com c senão imprime_na_saida([D.código(cadeia), c]) D.insere(cadeia concatenada com c) cadeia = '' fim se fim enquanto imprime_na_saida([D.código(cadeia), ''])
A decodificação se dá de forma similar, começamos com o dicionário apenas com o código para a cadeia vazia, e vamos lendo os pares de (Dseq, c). Para cada par lido, emitimos na saída a sequência presente no dicionário sob o código Dseq, concatenada com o caractere c. Em seguida adicionamos esta nova sequência no dicionário. Note que o algoritmo de manutenção do dicionário (atribuição de códigos às sequências) deve ser o mesmo no programa que codifica e no que decodifica, para não termos inconsistências.
Para exemplificar o uso do algoritmo vamos aplicá-lo à entrada "A_ASA_DA_CASA". A tabela abaixo representa cada passo (determinado pela leitura de um novo caractere na entrada), com as respectivas saídas, quando ocorrerem, e o conteúdo do dicionário (expresso na forma [código:cadeia, código:cadeia, … código:cadeia]):
c | cadeia | saída | D |
A | '' | (0, 'A') | [0:'', 1:'A'] |
_ | '' | (0, '_') | [0:'', 1:'A', 2:'_'] |
A | '' | - | - |
S | 'A' | (1, 'S') | [0:'', 1:'A', 2:'_', 3:'AS'] |
A | '' | - | - |
_ | 'A' | (1, '_') | [0:'', 1:'A', 2:'_', 3:'AS', 4:'A_'] |
D | '' | (0, 'D') | [0:'', 1:'A', 2:'_', 3:'AS', 4:'A_', 5:'D'] |
A | '' | - | - |
_ | 'A' | - | - |
C | 'A_' | (4, 'C') | [0:'', 1:'A', 2:'_', 3:'AS', 4:'A_', 5:'D', 6:'A_C'] |
A | '' | - | - |
S | 'A' | - | - |
A | 'AS' | (3, 'A') | [0:'', 1:'A', 2:'_', 3:'AS', 4:'A_', 5:'D', 6:'A_C', 7:'ASA'] |
EOF | '' | (0, '') | - |
A sequência de saída seria da forma: (0,'A')(0,'_')(1,'S')(1,'_')(0,'D')(4,'C')(3,'A'). Se usarmos três bits para representar os códigos das entradas do dicionário (valor máximo de 7) e um byte para os caracteres normais teríamos um total de 77 bits para representar a sequência (originalmente com 104 bits—13 caracteres com um byte por caractere).
O clássico problema dos algoritmos baseados em dicionários é a memória necessária. Quanto mais lemos dados do arquivo, mais sequências armazenamos no dicionário, e com isso, necessitamos de mais memória. O outro problema que isso causa é de espaço de endereçamento: os códigos das entradas no dicionário crescem junto com ele (em geral ocupam bits, onde N é o tamanho, ou número de entradas, do dicionário). Várias abordagens podem ser adotadas para lidar com esse problema, as mais simples são:
Outro problema, esse específico do LZ78, é o crescimento lento do dicionário. Devido a característica de inserir as cadeias no dicionário assim que um único caractere quebra a sequência faz com que o dicionário cresça de forma lenta e só se torne realmente útil depois de bastante informação lida. Esse problema torna o LZ78 e seus derivados pouco apropriado para comprimir quantidades muito pequenas de dados. A abordagem dada pelo LZ77 pode ser útil nos casos onde o crescimento lento do dicionário venha a reduzir a compressão.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.