En 1978, Ziv y Lempel publicaron un nuevo método de compresión de datosque ha tenido también mucho éxito, el LZ78 [25]. Lo realmente interesantede este algoritmo es la representación recursiva que utiliza el diccionario. Esteestá compuesto por pares wk donde w es una posición dentro del diccionarioy k es un símbolo sin codificar.
El compresor genera códigos wk cada vez que inserta una nueva entrada en eldiccionario. De esta manera el descompresor consigue reconstruir una copiaexacta del diccionario que usó el compresor en cualquier instante.
Aunque los códigos wk utilizan más bits que los símbolos originales, elcompresor sólo envía un código al descompresor cuando una nueva cadenawk es insertada en el diccionario.
En realidad, wk representa a la cadena formada por la concatenación dela “cadena” w con el símbolo k. Es importante darse cuenta de que wes físicamente un número entero positivo, aunque representa a una cadenaporque apunta a una dirección dentro del diccionario donde hay otra w′k′.Llamaremos a este proceso de concatenación “string(w)”, que finaliza cuandow = 0 (la entrada de índice 0 en el diccionario, la cadena vacía).
La principal ventaja de LZ78 frente a LZ77 radica en que la longitud máximade la cadena encontrada ahora no está limitada por el tamaño del look-aheadbuffer, sino por el tamaño del diccionario que suele ser mucho mayor.