3.5: Diccionario dinámico

Última actualización
Guardar como PDF

Page ID: 82076

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}}\)

Lo que sería mejor para muchas aplicaciones sería un esquema de codificación usando un diccionario que se calcula sobre la marcha, ya que el mensaje se procesa, no necesita acompañar al mensaje, y se puede usar antes de que se haya procesado el final del mensaje. A primera consideración, esto puede parecer imposible. Sin embargo, tal esquema es conocido y de amplio uso. Es la técnica de compresión LZW, que lleva el nombre de Abraham Lempel, Jacob Ziv y Terry Welch. Lempel y Ziv en realidad tenían una serie de técnicas, algunas veces referidas como LZ77 y LZ78, pero la modificación por Welch en 1984 le dio a la técnica todas las características deseadas.

Welch quería reducir el número de bits enviados a un cabezal de grabación en unidades de disco, en parte para aumentar la capacidad efectiva de los discos, y en parte para mejorar la velocidad de transmisión de datos. Aquí se describe su esquema, tanto para el codificador como para el decodificador. Ha sido ampliamente utilizado, en muchos contextos, para llevar a la compresión reversible de datos. Cuando se aplican a archivos de texto en una computadora típica, los archivos codificados suelen tener la mitad del tamaño de los originales. Se utiliza en productos de compresión populares como Stuffit o Disk Doubler. Cuando se usa en imágenes en color de dibujos, con grandes áreas que son exactamente del mismo color, puede dar lugar a archivos que son menores a la mitad del tamaño en comparación con los formatos de archivo en los que se almacena cada píxel. El formato de imagen GIF de uso común utiliza compresión LZW. Cuando se usan con fotografías, con sus cambios graduales de color, los ahorros son mucho más modestos.

Debido a que se trata de una técnica de compresión reversible, los datos originales pueden ser reconstruidos exactamente, sin aproximación, por el decodificador.

La técnica LZW parece tener muchas ventajas. Sin embargo, tenía una desventaja importante. No estaba disponible gratuitamente, estaba patentado. La patente estadounidense, número 4.558.302, expiró el 20 de junio de 2003, y las patentes en otros países en junio de 2004, pero antes de que lo hiciera, generó una polémica que sigue siendo un recuerdo desagradable para muchos por la forma en que se manejó.