Activa las notificaciones para estar al tanto de lo más nuevo en tecnología.

zopfli

Google trabaja en muchos frentes y uno de los más importantes es la programación. Se requiere de gente con talento para mantener funcionando el buscador, los servicios que ofrece, etcétera. Considerando que hay mucho código que se genera, sale una nueva propuesta de un compresor de archivos llamado Zopfli, el cual puede producir archivos zip 5% más pequeños, sin que haya efectos negativos para el usuario final. El único inconveniente es que es mucho más lento que el compresor zip.

Los algoritmos de compresión son frecuentemente asimétricos. Si se pueden ahorrar más bytes haciendo que el compresor logre esto haciendo más trabajo, esto puede beneficiar al descompresor pues no tendrá que hacer más trabajo. Esto es lo que hace el algoritmo LZ77 (llamado deflate), el cual es usado por una serie de programas compresores: Pkzip, etcétera, para así formar los archivos zip.

El LZ77 o Liv-Zempel es un método de compresión basado en un diccionario que escanea el archivo original y crea un diccionario de patrones de bits que se repiten en el archivo. La compresión se logra reemplazando los patrones de bits en el archivo con una referencia, que es el diccionario de tamaño fijo. Esto trabaja bien en la práctica y es la base del método deflate, el cual usa la compresión LZ77 que se sigue después de una codificación llamada Huffman.

Qué tan efectivo es el LZ77 depende de qué tamaño tiene el archivo original y qué tan frecuentes son las entradas en el diccionario. Si usted, por ejemplo, reemplaza muchas subcadenas con las referencias del diccionario, entonces la cantidad de espacio ahorrado depende de qué tan grande es el archivo y cuántas veces han ocurrido estas sustituciones en el archivo original.

Para que esto tenga sentido, la compresión de la información no debe perder ni un solo bit de la misma. Esto es, el archivo comprimido debe ser decodificado para ser idéntico al archivo original. Miedntras más empeño se ponga en ahorrar bytes, se puede lograr más porcentaje de espacio ahorrado sin menoscabo en las funciones del descompresor. Sin embargo, en la práctica es más complicado porque se usan dos métodos de compresión, LZ77 y Huffman, y ambos son modificables para lograr así más compresión en algunos casos.

Con todo esto, la llegada de Zopfli (llamado así por el pan que ilustra este artículo), el cual es un compresor escrito por la gente de Google, puede ayudarnos a comprender más estos asuntos de comprimir archivos. Es código abierto escrito en C y puede usarse para implementar una versión propia del algoritmo de compresión. Logra entre 3% y 8% de ahorro más que el programa zip implementando un método de búsqueda exhaustiva para hallar el mejor diccionario. Se basa en un modelo de entropía iterante y en búsquedas de la trayectoria más corta para encontrar aquella que sea la de menos costo, considerando la gráfica de todas las representaciones de datos que pueda usar deflae.

Una vez comprimido el archivo con Zopfli, se puede descomprimir éste con gzip, zip, rar, entre otros. En otras palabra, todos ganan (bueno, casi), porque los archivos más pequeños son más rápidos de descargar, usan menos ancho de banda y ayudan a ahorrar batería en los dispositivos móviles. Sin embargo, Zopfli toma un 100% más de tiempo para comprimir que los programas tradicionales. Para los casos de tener que enviar un archivo comprimido muchas veces, puede -sin embargo- ser una buena opción.

Referencias:

Zopfli (código) 
Google Code (Blog) 

Desde la Red…
Comentarios