Problema del algoritmo LZW

El nombre completo del algoritmo LZW es codificación Rempel-Ziff-Welch, que es un algoritmo de compresión de datos. Está patentado, pero la mayoría de las patentes han caducado. Puede realizar una compresión simple de texto y la relación de compresión sigue siendo adecuada para ocasiones generales. Además, las imágenes GIF se utilizan con mayor frecuencia.

Hay varios conceptos importantes en el algoritmo LZW: caracteres, cadenas y tablas de codificación. Considera el flujo de datos como una secuencia de caracteres, organiza la secuencia de caracteres en una serie de cadenas, asigna un código a cada cadena y finalmente almacena el código de la cadena, ahorrando así espacio. Por ejemplo, ababba se puede representar como el código 1532 y 1523 se puede representar como 12 bits, lo que ahorra mucho espacio que el original de 5 * 8 bits. La tabla de codificación de LZW se crea dinámicamente y la misma tabla de codificación se puede recuperar del flujo de datos codificados, por lo que no es necesario guardar la tabla de codificación original al almacenar y transmitir datos. Esto también es diferente de algunas tablas de codificación fijas antes de la codificación. Los algoritmos son muy diferentes.

1. Proceso de codificación:

LZW es un algoritmo de codificación de longitud fija, es decir, la longitud de codificación de cada carácter o cadena es igual. Para facilitar la explicación, decidí usar 16 bits como codificación, el primero 255 como codificación de caracteres y los otros 256 y 257, que se explicarán en 3. Entonces la codificación de la cadena comenzará desde 258.

Todo el proceso de codificación es el siguiente:

1. Inicialice la tabla de codificación, codifique el número inicial y establezca la cadena actual en vacía;

2 .Lea un carácter, si es EOF, genere la cadena actual y finalice; de ​​lo contrario, ingrese 3;

3. Combine el carácter recién leído y la cadena actual para formar una nueva cadena. Si la nueva cadena aparece en la tabla de codificación, vaya a 2; de lo contrario, vaya a 4;

4. Agregue la nueva cadena a la tabla de codificación, asigne un número y establezca la longitud de la cadena actual. a N, ingrese el código de prefijo de longitud N-1 de la nueva cadena, establezca la cadena actual en el sufijo 1 de la cadena actual y luego ejecute 2.

2. Proceso de decodificación:

Para decodificar, lo único que necesitas saber es la longitud del código. Cada vez que se lee la longitud del bit correspondiente del flujo de codificación, se forma un código y luego, a través de este código, se puede encontrar la cadena correspondiente en la tabla de codificación y generarla. Dado que la tabla de codificación correspondiente no se almacena, la tabla de codificación debe construirse al mismo tiempo durante la decodificación.

El proceso de decodificación es el siguiente:

1. Inicialice la tabla de códigos y establezca el código anterior en vacío.

2. El código es fin, es fin. De lo contrario, continúe con 3;

3. Genere la cadena representada por el código. Si el código anterior no está vacío, agregue la cadena del código anterior y el primer carácter de la cadena actual a la tabla de códigos como una nueva cadena, establezca el código anterior como el código actual y ejecute 2.