3.7.2: Algoritmo LZW, Ejemplo 2

Última actualización
Guardar como PDF

Page ID: 82116

Paul Penfield, Jr.
Massachusetts Institute of Technology via MIT OpenCourseWare

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Codificar y decodificar el mensaje de texto

itty bitty nitty grrritty bin

(nuevamente, esta peculiar frase fue diseñada para tener cadenas repetidas para que el diccionario se forme rápidamente; también tiene una secuencia rrr de tres largos que ilustra un aspecto de este algoritmo).

El conjunto inicial de entradas del diccionario incluye los caracteres de la Tabla 3.3, que se encuentran en la cadena, junto con los caracteres de control para inicio y parada.

Tabla 3.3: LZW Ejemplo 2 Inicio del diccionario
32	espacio	114	r
98	b	116	t
103	g	121	y
105	i	256	iniciar
110	n	257	detener

Aquí se pueden aplicar los mismos algoritmos utilizados en el Ejemplo 1. El resultado se muestra en la Tabla 3.4. Tenga en cuenta que el diccionario se acumula con bastante rapidez, y hay una instancia de una entrada de diccionario de cuatro caracteres transmitida. ¿Fue efectiva esta compresión? Definitivamente. Un total de 33 caracteres de 8 bits (264 bits) fueron enviados en 22 transmisiones de 9 bits (198 bits, incluso incluyendo los caracteres de inicio y parada), para un ahorro de 25% en bits.

Hay un lugar en este ejemplo donde el decodificador necesita hacer algo inusual. Normalmente, al recibir una palabra de código transmitida, el decodificador puede buscar su cadena en el diccionario y luego emitirla y usar su primer carácter para completar la última entrada del diccionario parcialmente formada, y luego iniciar la siguiente entrada del diccionario. Por lo tanto, solo se necesita una búsqueda de diccionario. Sin embargo, el algoritmo presentado anteriormente utiliza dos búsquedas, una para el primer carácter y otra posterior para toda la cadena. ¿Por qué no utilizar una sola búsqueda para una mayor eficiencia?

Hay un caso especial ilustrado por la transmisión del código 271 en este ejemplo, donde la cadena correspondiente al código recibido no está completa. Se puede encontrar el primer carácter pero luego antes de que se recupere toda la cadena, se debe completar la entrada. Esto sucede cuando un carácter o una cadena aparece por primera vez tres veces seguidas, y por lo tanto es raro. El algoritmo anterior funciona correctamente, a un costo de una búsqueda adicional que rara vez se necesita y puede ralentizar el algoritmo. Un algoritmo más rápido con una sola búsqueda de diccionario funciona de manera confiable solo si detecta esta situación y la trata como un caso especial.

Tabla 3.4: Resumen de transmisión del Ejemplo 2 de LZW