Los algoritmos de compresión siguen evolucionando

Es muy probable que conozcas los archivos .ZIP, .RAR, .ACE y quizás hasta los 7z.

Salvo el último de la lista que fue introducido en 1999, los  algoritmos de compresión más conocidos tienen 20 años o más. Toda una vida, como diría la abuela.

Estamos muy familiarizados con estas extensiones y si a eso le sumamos el hecho de que por lo general los programas que usamos para “comprimir y descomprimir” nos han hecho la vida tan simple y que, por sobre todo – desde aquella esperada muerte de los disquetes – ya casi no nos preocupamos por “qué formato comprime mejor”. Por todas estas cosas, y también porque también ahora medimos la capacidad en terabytes, es notable como directamente pasamos por encima y casi ignoramos una de las cosas más fabulosas de la informática que es la compresión de datos. Al hacerlo, también pasamos por algo la forma en la que siguen evolucionando.

Siempre me gustó leer sobre algoritmos de compresión, quizás demasiado. Lamentablemente mi nivel en matemáticas me suele trabar cuando comienzan a aflorar explicaciones con integrales, matrices, derivadas y complejos cálculos. Y es que los algoritmos se tratan de justamente eso ya que desde el MP3 que estás escuchando, pasando por esta página web (que se comprime en gzip entre el servidor y tu navegador para ocupar menos ancho de banda) hasta la imagen que ilustra los posts… casi absolutamente todo lo que habituamos a utilizar está comprimido de alguna manera u otra.

Y tratar de entender (aunque sea poquito) el funcionamiento de éstas cosas, es alucinante.

Hoy me encontré bastante asombrado al ver el fabuloso ratio entre compresión y descompresión que logró un archivo 7zip que bajé. Está bien, dentro del mismo había documentos y son éstos formatos los que mejor se precian a la hora de demostrar las bondades de los nuevos formatos. Culpa del bichito curioso que entró a trabajar llegué a conocer nuevos algoritmos de compresión, que quizás sean estándares en un futuro, como lo son hoy .ZIP o .RAR, uno de los mas llamativos es PAQ, un algoritmo que no tiene ni su página en la Wikipedia en español, pero no importa, vamos a traducir un poquito acá para conocer más…

PAQ es un algoritmo de compresión sin pérdida de datos que se ha desarrollado a través de desarrollo colaborativo y actualmente se encuentra entre los primeros lugares en cuanto a medición de la relación de compresión  se refiere (aunque a expensas de la velocidad y el uso de la memoria). Versiones especializadas de PAQ han ganado el Premio Hutter y el Desafío de Calgary.

PAQ utiliza un algoritmo contexto de mezcla. Contexto mezcla se relaciona con la predicción por coincidencia parcial (PPM) en que el compresor está dividido en un predictor y un codificador aritmético, pero difiere en que la predicción de próxima símbolo se calcula utilizando una combinación ponderada de las estimaciones de probabilidad de un gran número de modelos condicionado a los diferentes contextos.

Genios de la compresión computacional

(¿La mafia rusa? No, son 5 de los mayores genios de la compresión del mundo mundial)

¿Vieron que términos tan raros? Lo interesante son los resultados, ahí es donde PAQ es absolutamente fabuloso. Para que nos demos una idea, en un test combinado (donde en un directorio se ponen imágenes JPG, BMP, GIF, música en MP3, videos, texto y otros arhivos) y se ponen a prueba los algoritmos, PAQ logra ratios de compresión superiores al 80%. De los “conocidos” mejor rankeados tenemos a Winzip y Winrar, con un 72% haciendo gala de sus mejores métodos de compresión en lo que respecta a sus formatos “estrella”. Porque también, no debemos confundir “programas” con “algoritmos” ya que por un término de compatibilidad Winzip abre RAR, Winrar abre ZIP y 7zip los abre todos, y es gratis, de paso.

Es notable como, si bien la implementación de los algoritmos no es tan rápida en la informática hogareña (debido a que la capacidad en discos y la velocidad de conexiones aumentó en forma mucho mayor que la necesidad de más compresión) en el ámbito académico se sigue buscando el límite matemático a la compresión de datos. De hecho, esos premios de los que habla el texto de la Wikipedia son financiados por universidades o docentes. Curiosamente el premio Hutter destina 500 euros por cada 1% que se le pueda sumar al record de compresión de un archivo de texto de 100MB que son, ni nada más ni nada menos, los 100.000.000 primeros caracteres de la enciclopedia online.

Ah, y para terminar, y si pensás que estos algoritmos son solamente una carrera de geeks locos similares al Doctor Locovick de los autos locos, dejame decirte que estos avances sí se ven en la vida real. Bueno, si bien no es real del todo, lo podés ver habitualmente al bajarte una película o un capítulo de serie comprimido en x.264.

29 Comentarios

  1. A mi me llama la atencion que aun no halla salido un 7zip, winrar en openCL.

    Seria fabuloso que la compresion lo haga la GPU.

  2. Tendrías que probar el KGB archiver http://sourceforge.net/projects/kgbarchiver/ con el cual ha visto distribuciones de linux de 600 y mas megas en el tamaño de un disquette de 3 1/2 (1.44 mb).

    Como contra tarda unos 15 días en lograr esa compresión “extrema” pero los resultados son impresionantes.

    Saludos.

  3. Guille, a mí tambien me interesa el tema, leí bastante y cada vez que puedo vuelvo a leer y entiendo un cachito mas. Por el trabajo uso mucho archivos comprimidos, muchas veces separados en partes para poder enviarlos por mail, y la verdad es que quizas el 7zip abra winrar/winzip, pero cuando las papas queman, el que gana siempre es Winrar, no hay con que darle.
    Si por ejemplo recibo un archivo comprimido en partes, y una de las partes no llega o esta corrupta, con el Winrar se puede ver y extraer por lo menos los archivos que estan usables de lo que llegó, y así un montón de features que siempre estan por encima de Winzip o 7zip. Archivos ISO? CAB? 7ZIP? RAR? a cualquiera le entra!!!!

    Hize algunas comparativas, y sí, a veces algun programa es un cachito más rápido (Winrar siempre me dió la impresión de ser mas lento), o comprime un poquito más (cuanto, 2%? 4%? más de eso no existe en la informática práctica, cuando aparece algun compresor sin pérdida con ratios muy grandes siempre termina siendo chamuyo…)…

    Así que… larga vida al WinRAR!!!!!

  4. Aunque a veces no entiendo un pomo del tema, es una cosa apasionante el campo de la matemática. Las cosas que se pueden hacer y desarrollar es increíble.

    Muchas veces no me entra en la cabeza, y no se como hacen algunos tipos para tener TAL nivel de abstracción. Es simplemente demasiado para mi cerebro… y eso que soy cabezón! Debería tener mas lugar jajaja.

  5. Es ABSOLUTAMENTE MENTIRA que en un diskette de 1,44 entre una distro Linux de 600 Mb. De hecho es ABSOLUTAMENTE MENTIRA superar ni siquiera en un 30 % la capacidad de compresión de los mas conocidos compresores.

    Ahora si vos metes miles de archivos de texto, les cambiás el nombre haciendo creer que es una distro, le haces creer a cualquier desprevenido que se pueden meter 100 Mb de cualquier cosa en la capacidad de un diskette.

    • Seguro? Tan seguro como para hablar en mayúsculas? Yo he bajado archivos de poquísimos megas y tenía la ISO de un CD, funcional

      No recuerdo ahora exactamente que era, pero cuando bajé eso me quedé de culo

    • Hola! El KGB archiver es verdad que comprime tanto. Una vez baje un juego comprimido que pesaba 128MB y descomprimido pesaba mas de 4GB. Saludos

    • Yo baje 20 mb y al descomprimirlo (24hs) tenia un iso de un juego de 3.8 gB totalmente funcional, con el KGB.

    • Es totalmente inútil hacer eso. Si querés comprimir más podés seleccionar un nivel de compresión mayor o buscar un algoritmo más eficiente (por ejemplo rar o 7z son bastante más eficientes que el zip). Comprimir un zip dentro de otro no hace que ocupe menos espacio (o si lo hace, igual podrías haberlo logrado especificando un nivel de compresión mayor en el zip original).

  6. Alguien sabe si es confiable 7zip beta? Para mí este es de los mejores que encontré, por arriba del winrar… El kbg pinta interesante, pero nunca lo probé mucho…

    • El KGB para comprimir mucho usa algoritmos que toman muuuucho tiempo. En general no es práctico.

    • Yo nunca tuve problemas y siempre uso la versión beta, pero tampoco noto muchas diferencias con respecto a la final. Podés ver los cambios entre la 9.20 y la 9.22 en http://www.7-zip.org/history.txt para decidir si hay algo que te interese o si no vale la pena usar el beta.

  7. A ver, tal vez no se entendió… podés tener una ISO de muchos Mb partiendo de algo mucho mas chico dependiendo del tipo de archivos a comprimir, si la mayoría de archivos son del tipo TXT o altamente comprimibles como los BMP se cumple de manera sorprendente. Lo que no se cumple BAJO NINGUN CONCEPTO es una distro de CUALQUIER sistema operativo de ni tan siquiera 300 Mb en un diskette ni en 3 o 4… es mas, Office 2003 que son unos 300 Mb solo comprime un 3 % como mucho. Yo no he visto, yo lo he hecho con esa herramienta y NO SE CUMPLE en nada.n NO ENTRA en un diskette ni en 3 ni en 5 ni en 10, una distro de 300 MB, ni el Office ni Windows XP, es como decir que comprimiste miles de fotos de formato JPG en la mitad del espacio, NO SE CUMPLE, NO SE PUEDE, NO HAY COMO.
    .-

    • Sera porque los jpg, mp3, mp4 son formatos ya comprimidos incluso muchos .doc son en realidad un zip con el documento dentro (abri un .doc con 7zip y llevate una sorpresa). El cd de Office como todos los de microsoft lleva archivos cab (ms-cabinet) los cuales con contenedores igual que rar o 7z… no se puede comprimir mucho algo que ya ha sido comprimido (entropia). Tendrias que fijarte bien que tipo de archivos tenes que comprimir.

      Tecnicamente si es posible cargar un NUCLEO linux en uno o varios disquetes… sino anda a /boot y fijate el tamaño que tiene los vmlinuz y kernel…. ahora compilando el kernel bien especifico para tu pc se puede reducir aun más. el caso mas simple es el pequeño firmware busybox (linux) que suelen llevar los router y los cds/disquetes netinstall que cargan un kernel de pocos megas.

      • No tiene nada que ver que puedas tener un linux que quepa en un diskette. Él habla de comprimir una distro de 300MB en ese espacio, y da distintos ejemplos de cosas que usamos día a día que no tienen posibilidad de comprimirse sustancialmente, sin importar el algoritmo que usemos, nada más.

        • el comentario que hice de linux era para responder lo que el mismo dijo arriba y con mayusculas… busybox entra facilmente en un disquete (no sera un entorno de escritorio, pero permite hacer algunas ordenes simples) y los sistemas linux siempre estan comprimidos (initrd, initram) y es necesario descomprimirlos al arrancar…. no seran 300 o 600 que se descompriman en la memoria pero seran mas de los 1.44 que estaban en el disquete
          Con respecto a lo que escribiste abajo… si es cierto no me fije el tipo de compresion… doc no usa zip (quiza porque es bastante antiguo)… pero si docx, y odt recien lo comprobe, gracias por el dato, saludos.

        • Oka, perdón si mi comentario sonó mala onda (ahora lo leo de vuelta y parece que si), no era la intención.
          Sí, sabía que hay distros que caben en un diskette, aunque pensaba más en algo al estilo de muLinux, que esté pensado como distro en sí, pero es cierto, hay muchas que usan busybox en dispositivos embebidos con ROMs a veces hasta más chicas que un diskette.
          Yo interpreté lo que decía Fer como diciendo “si las posibilidades técnicas (o matemáticas) de comprimir fueran tales como para poder tener una distro completa de 300MB al instalarse comprimidas en un diskette, la compresión realmente valdría la pena, pero eso lamentablemente es totalmente imposible”. Por eso, pensé que no importaba si en verdad hay o no hay distros que SI quepan en un diskette, porque para mí no era ese el sentido de su comentario, pero no hay drama.
          Ah, no sabia que el docx es zip también! Yo nunca lo uso… llevo el LibreOffice en mi corazón jaja!
          Saludos!

      • Y sí, el 7z abre los .doc, pero no es que sean un .zip, creo que son un formato propietario que MS denomina Windows Compound Binary File Format, y que el 7z lo que hace es mostrarte cada uno de los streams contenidos en este como un archivo (algunos de estos streams pueden corresponderse con los archivos embebidos en el documento, y los otros son propiedades, contenido, etc). No sé si tienen compresión aplicada y de qué forma.

        Los que sí son literalmente un .zip son los .odt (OpenDocument).

        • Brenda: los “chicos” piensan que con el 7zip “ven” los archivos “doc” pero no entienden que el 7zip solo los “descomprimen”, y con todo el respeto lo digo, llegué a leer los comentarios hasta este punto y veo que algunos no diferencian un doc de un zip, o creen en lo que leyeron en algun lado en internet que pueden tener un office en 1.44 mb y lo toman como cierto aun sin haberlo comprobado, hevisto hace años un supuesto office “comprimido” en 0,5 mb que daba vueltas en el kazaa o algún sitio en internet, nunca lo probé, igual no creo en eso.

          Pero si pudiera haber algo que comprima tanto se tardaría horas en descomprimirlo, no? por eso no creo que sea practico estar horas esperando a que termine de hacerlo.

  8. Es mas, desafío a cualquiera que logre un 5 % de compresión de una foto de cuaqluier camara en formato JPG, prueben con el programa que quieran y no crean la burrada que dijeron mas arriba de que pasaron 15 días!!!

    • Por supuesto que el “problema” es que el JPG ya está compimido. No podés pretender comprimir algo que ya esta cerca de la entropía máxima. Es más, jpeg es un algoritmo con pérdida, se ha descartado información para poder llevar a cabo la compresión.

      Ahora, si tenes varias fotos JPG parecidas, y las comprimís todas en un archivo sólido de diccionario suficientemente grande sí podrías llegar a ver una reducción de espacio considerable.

  9. Creo que con insultar y desmerecer la opinión de los demás no se aporta nada nuevo a la conversación.
    Ahora si te pusieras a leer y comprobaras que estoy equivocado, con gusto aceptaría mi error.
    Saludos

  10. Alfredo, sin ánimo de ofender a la persona, lo de burrada es por la aseveración, la aseveración esa es una burrada, la persona que lo dijo es sumamente respetable, muy buen amigo y muy amigo de sus amigos y tal vez un excelente padre de familia, pero algo es claro, no comprobaste nunca lo que aseveras y sí… yo ya comprobé que eso es una falacia, te gusta mas? en otras palabras, me puse a comprobarlo y de puro porfiado hice pruebas de compresión con ese programa y obtuve resultados de compresión marginales, le dediqué mucho tiempo en su oportunidad porque también me creí esa posibilidad y efectivamente, NO LO HACE, NO SE CUMPLE, NO SE PUEDE.

    Sin embargo coincido con algunas conclusiones generales: Winzip es el mas rápido y WinRar comprime un poco mejor, 7Zip lo probé y la verdad que no fué la gran diferencia, tal vez haya pesado la antiguedad de WinRar que para mí es por lejos el mas y mejor manejable sin tanta historia.

    Agustín, hacelo entonces con ejecutables querés?

    La cuestión es combatir la brujería técnica de decir muy sueltos de cuerpo que en un diskete entra una distro de Linux de 600 Mb, NO ENTRA, NO SE PUEDE, NO EXISTE eso.

    Como tampoco entra un Office de 300 Mb ni siquiera en 100 diskettes.

    • yo creo que es una “tactica de publicidad” por parte del sitio para que uno descargue ese programa creyendo que hace “más” que otros, tal vez sea eso.

      El kgb lo probé pero no comprime mas que winzip o que winrar.

  11. Yo uso winzip, tiene una taza menor de compresión vs rar y 7zip, pero hace su tarea rápido mientras rar y 7zip, necesita mucho poder de parte de la PC para ahorrarse un 2% a 5% mas, que con lo anchos de banda y las capacidades de almacenamientos actuales, nos es prioridad cuando necesita mandar algo con premura.

Dejar respuesta

Please enter your comment!
Please enter your name here