[ Foro de C ]

Compresión de archivos.

Holaaa!

He estado estudiando algunos tópicos de programación relacionados con la compresión, y hay algo que me tiene muy intrigado.

Lo que pasa es que, como bien sabemos, es imposible crear un algoritmo que comprima "cualquier archivo", lo cual implica que debe existir una probabilidad de compresión.
Eso significa que para cualquier algoritmo existen muchos "archivos incompresibles". Sin embargo jamás he escuchado de alguien que haya encontrado un archivo incompresible de "WINZIP" ni "WINRAR", etc... (esto sin considerar los archivos que ya están comprimidos...).

Entonces me pregunto:
Cómo es posible que, habiendo tantos archivos incompresibles, nadie jamás haya encontrado alguno?
Cuál es la probabilidad de compresión de, por ejemplo, WinZip? Por qué?

De antemano muchas gracias!
Adiós.

---

La mayoría de los formatos comprimidos son "casi incompresibles".  Por ejemplo, si intentas comprimir en formato ZIP un fichero que ya está comprimido en ZIP, la ganancia será muy baja, o puede incluso ocurrir que el fichero resultante sea mayor que el original.

Lo mismo ocurre con la mayoría de formatos comprimidos, como JPG, GIF, AVI (en subformatos que sí compriman), MP3, etc.

La idea es que para comprimir se aprovecha la entropía del fichero, su orden interno, buscando patrones repetitivos. Cuando se comprime, estos patrones repetitivos desaparece, y entonces uno se puede comprimir más usando el mismo método (aunque quizá sí con otro método alternativo, que esté diseñado para ese tipo de ficheros).

En cuanto a factor de compresión, depende mucho del tipo de fichero. Por ejemplo, un fichero de texto puro en inglés se puede comprimir cerca de un 90%, mientras que un fichero MP3 es raro que se comprima mucho más de un 1% (y eso es gracias a las cabeceras). En general, RAR suele comprimir cerca de un 10-15% que ZIP, ACE algo similar, y 7Z un poco mejor. No te costará encontrar comparativas en Internet, como por ejemplo estas:

http://www.7-zip.org/

http://multiinstall.sourceforge.net/compress.html

http://jldugger.livejournal.com/3722.html

---

Gracias por la respuesta.
...pero aún sigo sin entender lo siguente:

No existe un algoritmo que pueda comprimir TODOS los archivos.
Supongamos que consideramos TODOS los archivos hasta cierto tamaño, por ejemplo, unos 100MB. Independientemente de la "entropía", si hablamos de TODOS los archivos hasta 100MB, habrá inevitablemente archivos incompresibles para ese algoritmo.

Dado lo anterior:
Cómo es posible que WINZIP hasta ahora haya comprimido todo?
Son muy pocos los archivos incompresibles?
Cuál es la razón archivos_compresibles/archivos_incompresibles para Winzip?

Adios!

---

Eso de que Winzip haya comprimido todo es mucho decir. A mí se me ha dado más de un caso de que el fichero resultante ocupara más que el inicial.

Y, como ya te he comentado, con ciertos tipos de ficheros que ya están comprimidos, no se comprime nada o bien lo hace poquísimo.

Por ponerte algún ejemplo, voy a probar 4 ficheros reales escogidos al azar:

- Una captura de pantalla en formato PNG: de 273.381 bytes a 271.379 bytes (sí, lo ha comprimido algo, pero menos de un 1%).

- Ese fichero ZIP resultante del ejemplo anterior: de 271.379 a 271.676 (no lo ha podido comprimir más, al contrario, ha aumentado el tamaño resultante).

- Un fichero MP3 creado por mí con calidad normal: de 5.790.686 bytes a 5.778.011 (como antes: comprimido, pero menos incluso que antes, en este caso menos de un 0.25% y eso a pesar de las cabeceras, que son básicamente texto y se pueden comprimir más)

- Una imagen fotográfica JPG, de 258.127 bytes a 258.304 bytes: no lo ha comprimido, ha aumentado de tamaño.

¿Razón entre cantidad de ficheros compresibles e incompresibles?  Depende por completo del tipo de ficheros que intentes comprimir. Si coges un bloque de ficheros de texto, será el 100%; si coges imágenes JPG sin cabecera, o ficheros ya comprimidos en ZIP, o MP3 sin cabecera, puede llegar a ser el 0%.

Aun así, lo mejor es que tú mismo experimentes con los ficheros que te interesen en tu caso.

---

---