Introducción al algoritmo lz78

Aunque popular al principio, la popularidad de LZ78 disminuyó gradualmente, posiblemente porque algunos de los algoritmos de LZ78 estaban protegidos por patentes estadounidenses durante algunos de los años en que apareció LZ78. LZ78 La forma más popular de compresión es el algoritmo LZW, que es una variante de LZ78 desarrollado por Terry Welch.

Varios términos y símbolos utilizados en el algoritmo:

(1) Charstream: la secuencia de datos a codificar.

(2) Carácter: la unidad de datos básica en el flujo de caracteres.

(3) Prefijo: la secuencia de caracteres antes del carácter.

(4) Cadena de sufijo-símbolo: prefijo + carácter.

(5) Palabra de código: la unidad de datos básica en el flujo de palabras de código, que representa una cadena de caracteres en el diccionario.

(6) Flujo de código: la secuencia de palabras y caracteres de código es la salida del codificador.

(7) Diccionario: listado de afijos y símbolos. A cada cadena de sufijo se le asigna una palabra de código según su número de índice en el diccionario.

(8) Prefijo actual: utilizado en el algoritmo de codificación, se refiere al prefijo que se está procesando actualmente, representado por el símbolo p..

(9) Carácter actual: utilizado en el algoritmo de codificación, se refiere a los caracteres después del prefijo actual, representado por el símbolo c.

(10) Palabra de código actual: utilizada en el algoritmo de decodificación, se refiere a la palabra de código procesada actualmente, w representa la palabra de código actual, Cadena. w representa la cadena de sufijo de la palabra de código actual.