Mostrar código-fonte de LZ78

'''LZ78''' foi um dos [[algoritmo]]s 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.<ref name="salomon">{{citar livro|autor=SALOMON, David|título=Data Compression|subtítulo=The Complete Reference|editora=Springer|local-publicação=Nova Iorque|ano=2000|edição=2}}</ref>

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 [[patente]]s, e por isso não puderam se tornar populares durante algum tempo.<ref name="salomon" />

== Algoritmo ==
O [[algoritmo]] LZ78 usa um [[dicionário]] (que chamaremos de '''D''') para armazenar as sequências de [[caractere]]s encontradas no [[arquivo]], e usa os [[código]]s (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 ordenado|par]] ('''D'''<sub>seq</sub>, '''c''') onde '''D'''<sub>seq</sub> é 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'' := <nowiki>''</nowiki> # 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 = <nowiki>''</nowiki>
    '''fim se'''
  '''fim enquanto'''
  imprime_na_saida([''D''.código(cadeia), <nowiki>''</nowiki>])

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 ('''D'''<sub>seq</sub>, '''c'''). Para cada par lido, emitimos na saída a sequência presente no dicionário sob o código '''D'''<sub>seq</sub>, 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.

== Exemplo ==
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]):

{|border=1
|align="center"|'''c'''
|align="center"|'''cadeia'''
|align="center"|'''saída'''
|align="center"|'''D'''
|-
|A
|<nowiki>''</nowiki>
|(0, 'A')
|[0:<nowiki>''</nowiki>, 1:'A']
|-
|_
|<nowiki>''</nowiki>
|(0, '_')
|[0:<nowiki>''</nowiki>, 1:'A', 2:'_']
|-
|A
|<nowiki>''</nowiki>
| -
| -
|-
|S
|'A'
|(1, 'S')
|[0:<nowiki>''</nowiki>, 1:'A', 2:'_', 3:'AS']
|-
|A
|<nowiki>''</nowiki>
| -
| -
|-
|_
|'A'
|(1, '_')
|[0:<nowiki>''</nowiki>, 1:'A', 2:'_', 3:'AS', 4:'A_']
|-
|D
|<nowiki>''</nowiki>
|(0, 'D')
|[0:<nowiki>''</nowiki>, 1:'A', 2:'_', 3:'AS', 4:'A_', 5:'D']
|-
|A
|<nowiki>''</nowiki>
| -
| -
|-
|_
|'A'
| -
| -
|-
|C
|'A_'
|(4, 'C')
|[0:<nowiki>''</nowiki>, 1:'A', 2:'_', 3:'AS', 4:'A_', 5:'D', 6:'A_C']
|-
|A
|<nowiki>''</nowiki>
| -
| -
|-
|S
|'A'
| -
| -
|-
|A
|'AS'
|(3, 'A')
|[0:<nowiki>''</nowiki>, 1:'A', 2:'_', 3:'AS', 4:'A_', 5:'D', 6:'A_C', 7:'ASA']
|-
|EOF
|<nowiki>''</nowiki>
|(0, <nowiki>''</nowiki>)
| -
|}

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 [[bit]]s para representar os códigos das entradas do dicionário (valor máximo de 7) e um [[byte]] para os [[caractere]]s normais teríamos um total de 77 bits para representar a sequência (originalmente com 104 bits—13 caracteres com um byte por caractere).

== Problemas ==
O clássico problema dos [[algoritmo]]s baseados em [[dicionário]]s é a [[memória]] necessária. Quanto mais lemos [[dado]]s 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ço (memória)|endereçamento]]: os [[código]]s das entradas no dicionário crescem junto com ele (em geral ocupam <math>log_2(N)</math> [[bit]]s, 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:
* Congelamento do dicionário (quando o dicionário atinge o tamanho limite, ele fica "congelado" e mais nenhuma entrada pode ser adicionada nele).
* Esvaziamento (o dicionário é esvaziado e a compressão começa toda de novo). Essa técnica pressupõe que é mais vantajoso usar a redundância local que a redundância global para a compressão. corresponde a separar o arquivo em "blocos" comprimidos separadamente.
* Uso de uma política de esvaziamento que seja comum tanto ao compressor quanto ao descompressor (apagar entradas mais antigas, por exemplo).

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.

{{referências}}

== Bibliografia ==
* ZIV, Jacob, LEMPEL, Abraham; [http://www.cs.duke.edu/courses/spring03/cps296.5/papers/ziv_lempel_1978_variable-rate.pdf ''Compression of Individual Sequences Via Variable-Rate Coding''], IEEE Transactions on Information Theory, September 1978.

{{esboço-prog}}

[[Categoria:Algoritmos de compressão de dados]]