desinflar
deflate es el algoritmo utilizado en los formatos de archivo comprimido zip y gzip ( .gz ), internamente en documentos de Office como .docx y .xlsx , archivos Java ( .jar ) y en páginas web comprimidas a través de HTTP. El formato de imagen .png utiliza un algoritmo de predicción de píxeles seguido de la compresión de los errores de predicción residuales con desinflado.
desinflar no es el mejor algoritmo de compresión. En la Prueba comparativa de compresión de texto grande, gzip y zip se clasifican en 142 y 143 de 195 por relación de compresión. Muchos de los programas de mayor rango también son más rápidos. Entonces te estarás preguntando por qué es tan popular. Es porque ha existido durante mucho tiempo (desde PKZIP en 1993), no está gravado por patentes, y hay programas gratuitos y de código abierto (gzip, Info-Zip) y bibliotecas (zlib). El formato desinflado es un estándar de Internet documentado en RFC 1951. Aunque muchos algoritmos nuevos y mejores también son gratuitos y están bien documentados, los estándares de software tardan mucho tiempo en ser ampliamente aceptados.
- ¿Cuánto tiempo se necesita para leer Introducción a Algoritmos de TH Cormen, para un principiante?
- ¿Cuál es el código / algo para la multiplicación de matriz dispersa?
- ¿Por qué se utilizan montones para la asignación de memoria? ¿Por qué no se utilizan pilas ni ninguna otra?
- Algoritmos: ¿Cómo la combinación de ordenamiento tiene complejidad espacial O (n) para el peor de los casos?
- ¿Puede un gráfico ser un circuito de Euler y una ruta al mismo tiempo?
deflate utiliza LZ77. Se comprime reemplazando cadenas duplicadas con punteros a ocurrencias anteriores. Los literales, las compensaciones de coincidencia y las longitudes de coincidencia se codifican luego con Huffman utilizando tablas de Huffman que se transmiten junto con los datos comprimidos. La razón de la baja relación de compresión es que las compensaciones de coincidencia están limitadas a 32 KB, por lo que podría ejecutarse en computadoras de principios de los años 90 con solo 64 KB de memoria. Los formatos más nuevos como RAR, 7Z, LZ4, ZPAQ y ZSTD permiten compensaciones más grandes pero requieren una memoria al menos igual al desplazamiento máximo para descomprimir.