3.7.1: Algoritmo LZW, Ejemplo 1
- Page ID
- 82117
Considere la codificación y decodificación del mensaje de texto
itty bitty bit bin
(esta peculiar frase fue diseñada para tener cadenas repetidas para que el diccionario se acumule rápidamente).
El conjunto inicial de entradas del diccionario es código de caracteres de 8 bits con puntos de código 0—255, con ASCII como los primeros 128 caracteres, incluidos los de la Tabla 3.1 que aparecen en la cadena anterior. La entrada 256 del diccionario se define como “diccionario claro” o “inicio”, y 257 como “fin de transmisión” o “parada”. El mensaje codificado es una secuencia de números, representando los códigos las entradas del diccionario. Inicialmente la mayoría de las entradas del diccionario constan de un solo carácter, pero a medida que se analiza el mensaje se definen nuevas entradas que representan cadenas de dos o más caracteres. El resultado se resume en el Cuadro 3.2.
| 32 | espacio | 116 | t |
| 98 | b | 121 | y |
| 105 | i | 256 | iniciar |
| 110 | n | 257 | detener |
Algoritmo de codificación: Define un lugar para mantener nuevas entradas de diccionario mientras se están construyendo y llamarlo nueva entrada. Comience con nuevo-entrada vacía, y envíe el código de inicio. Después agrega a la nueva entrada los caracteres, uno por uno, de la cadena que se está comprimiendo. Tan pronto como la nueva entrada no coincida con ninguna entrada de diccionario existente, ponga nuevo-entrada en el diccionario, usando el siguiente punto de código disponible, y envíe el código para la cadena sin el último carácter (esta entrada ya está en el diccionario). Después usa el último personaje recibido como el primer personaje de la siguiente nueva entrada. Cuando termine la cadena de entrada, envíe el código para lo que esté en la nueva entrada seguido del código de detención. Eso es todo lo que hay para ello.
Para beneficio de quienes aprecian ver algoritmos escritos como un programa de computadora, este algoritmo de codificación se muestra en la Figura 3.5. Cuando este procedimiento se aplica a la cadena en cuestión, el primer carácter
es “i” y la cadena que consiste solo en ese carácter ya está en el diccionario. Entonces el siguiente carácter se agrega a la nueva entrada, y el resultado es “it” que no está en el diccionario. Por lo tanto, la cadena que estaba en el diccionario, “i”, se envía y la cadena “i t” se agrega al diccionario, en la siguiente posición disponible, que es 258. El nuevo ingreso se restablece para que sea solo el último personaje, que no fue enviado, por lo que es “t”. Se agrega el siguiente carácter “t” y el resultado es “tt” que no está en el diccionario. El proceso se repite hasta que se alcanza el final de la cadena.
Durante un tiempo al principio las entradas adicionales del diccionario son todas cadenas de dos caracteres, y hay una cadena transmitida por cada nuevo carácter encontrado. Sin embargo, la primera vez que se repite una de esas cadenas de dos caracteres, se envía su código (usando menos bits de los que se requerirían para dos caracteres enviados por separado) y se define una nueva entrada de diccionario de tres caracteres. En este ejemplo sucede con la cadena “i t t” (este mensaje fue diseñado para que esto suceda antes de lo que se esperaría con el texto normal). Más adelante en este ejemplo, se transmite el código de una cadena de tres caracteres y se define una entrada de diccionario de cuatro caracteres.
En este ejemplo, los códigos se envían a un receptor que se espera que decodifique el mensaje y produzca como salida la cadena original. El receptor no tiene acceso al diccionario del codificador y por lo tanto el decodificador debe construir su propia copia.
Algoritmo de decodificación: Si se recibe el código de inicio, borre el diccionario y establezca la nueva entrada vacía. Para el siguiente código recibido, dé salida al carácter representado por el código y también colóquelo en nueva entrada. Después, para los códigos posteriores recibidos, anexa el primer carácter de la cadena representada por el código a la nueva entrada, inserta el resultado en el diccionario, luego da salida a la cadena para el código recibido y también colócala en nuevo-entrada para iniciar la siguiente entrada del diccionario. Cuando se recibe el código de parada, no hay que hacer nada; se puede abandonar la nueva entrada.
Este algoritmo se muestra en formato de programa en la Figura 3.6.
Tenga en cuenta que el codificador y el decodificador crean cada uno el diccionario sobre la marcha; por lo tanto, el diccionario no tiene que transmitirse explícitamente, y el codificador trata el texto en una sola pasada.
¿Funciona esto, es decir, se reduce el número de bits necesarios para la transmisión? Enviamos 18 caracteres de 8 bits (144 bits) en 14 transmisiones de 9 bits (126 bits), un ahorro de 12.5%, para este ejemplo muy corto. Para el texto típico no hay mucha reducción para cadenas de menos de 500 bytes. Los archivos de texto más grandes a menudo se comprimen por un factor de 2, y los dibujos aún más.