El Hutter Prize for Compression of Human Knowledge es un peculiar reto medio informático medio matemático propuesto por Marcus Hutter, Matt Mahoney y Jim Bowery, quienes tienen 50.000 euros esperando como premio para quien consiga comprimir sin pérdidas un archivo que contiene 100 MB¹ de textos de la Wikipedia en menos de 16 MB.
El reto lleva en marcha desde agosto de 2006. Un matiz es que en realidad el premio es de 500 euros por cada 1% de mejora sobre los tamaños anteriores, de modo que se va repartiendo y ya hay quien ha «repetido» pequeños premios con sucesivas mejoras.
Las reglas completas evitan los trucos y trampas triviales: obligan a que el programa sea autosuficiente y no pueda hacer conexiones externas. Tampoco puede acceder a ficheros o diccionarios fuera de sí mismo (aunque el programa se puede presentar tanto como autoextraíble como un programa + fichero de datos comprimido). Debe correr sobre una instalación estándar de Windows o Linux. Además, debe poderse ejecutar en menos de diez horas en un Pentium 4 corriente. El reto es lícito y está bien planteado; las reglas no son demasiado estrictas pero obviamente los organizadores eliminarán a la fauna habitual de los concursos que considera que «ganar» implica «esquivar las reglas y ser más listo que nadie» en vez de cumplir lo que sea ha planteado, simple y llanamente: inventar la mejor compresión de datos posible.
El fichero con el contenido original de la Wikipedia en inglés es invariable y se llama enwik8 [ZIP; 33 MB – con lo que se ve que usando un compresor zip no se gana el premio ;-] Se trata del mismo fichero que se utiliza en el Large Text Compression Benchmark, unas pruebas comparativas de compresión sin pérdidas que gestiona Matt Mahoney, uno de los organizadores. Contiene algo de código HTML y de marcado de Wiki, pero por lo demás es todo texto ASCII en inglés.
La motivación del reto la describen así en su página web:
Este Concurso de Compresión está motivado por el hecho de que ser capaz de comprimir bien está íntimamente relacionado con actuar de forma inteligente, reduciendo de ese modo el escurridizo concepto de ingeligencia a una simple cuestión de tamaños de ficheros. Para comprimir los datos hay que encontrar regularidades en ellos, lo cual es intrínsicamente difícil (muchos investigadores viven de analizar datos y encontrar modelos compactos). De modo que los nuevos compresores capaces de batir a los «compresores tontos» deben ser más inteligentes. Como el premio pretente estimular el desarrollo de compresores inteligentes «universales», emplea un corpus de datos «universal». Podría decirse que Wikipedia, la enciclopedia en línea, es una buena fotografía de todo el conocimiento humano. De modo que el compresor definitivo debería «comprender» todo este conocimiento humano, es decir, ser realmente inteligente. [El fichero] enwi8 es probablemente un honroso representante en forma de extracto de la Wikipedia.
Suena un poco extraño. Y supongo que se puede estar más o menos de acuerdo con las teorías de los organizadores y la forma de expresarlas – alguien decía jocosamente que les faltaba incluir algo sobre conseguir «un impulsor inverso de taquiones ante la escasez de cristales de dilitio para poder atravesar el campo de curvatura de neutrinos». En cualquier caso, en el fondo se trata de un concurso aparentemente sencillo y abierto en el que quien presente un programa más eficiente puede reclamar su premio. Una sencilla cuestión de números.
El récord más reciente lo tiene Alexander Ratushnyak, quien dejó los 100.000.000 bytes originales del enwi8 en sólo 16.481.655 bytes. Ratushnyak empleó una versión tuneada de un compresor llamado PAQ que se basa en un algoritmo predictivo. Este sistema emplea diccionarios hechos a medida capaces de «acertar» con gran probabilidad cuál será la siguiente palabra de un texto, basándose en la idea de que hay ciertas palabras relacionadas sintácticamente y semánticamente, lo cual ayuda a comprimirlas en el menor tamaño posible. (Algunos teléfonos móviles cuentan con una versión de estos sistemas predictivos letra a letra para permitir teclear más rápido las palabras de los SMS.)
Todo esto me recordó por cierto al famoso reto, fiasco y divertidísima historia llamada The $5000 Compression Challenge, un reto similar que fue «ganado» llevando un poco al límite los métodos y las reglas. Al parecer ese reto partió de la extensa relación de sistemas de compresión imposibles e inútiles en Compression of random data (WEB, Gilbert and others) (parte del FAQ del grupo comp.compression) con historias muy divertidas estilo máquinas de movimiento perpetuo, como la patente absurda número 5,488,364, capaz de comprimir datos aleatorios de forma recursiva (una y otra vez)… ¿Que queda al final? Curiosas historias todas ellas que cualquiera interesado en estos temas debería leer en detalle.
Se puede leer algo más sobre el Premio Hutter en la Wikipedia, donde también hay bastante información sobre los sistemas de compresión PAQ, que se pueden usar con licencia GPL en cualquier proyecto que requiere minimizar el espacio ocupado por los datos.
(Vía Slashdot.)
¹ Megabytes y Megabytes – La nota curiosa es que el fichero original del Premio Hutter contiene exactamente 100 millones de bytes y se refieren a él como «100 MB». En mi pueblo informáticamente un MB solía considerarse 1.048.576 bytes (1024 × 1024). El caso es que me lo bajé para comprobarlo y son 100 millones de bytes exactos. Pero he ahí la frase del siglo: «Que un MB sea una cosa o la otra depende de si eres un geek o un pedante» dice el original, prefiendo 1 MB para 106 bytes (versión pedante) en vez de 1 MB para 220 bytes (versión informática binaria). Así que el reto se resumiría más exactamente como comprimir 100 millones de bytes en menos de 16 mllones de bytes (y no en 16.777.216, que serían «16 MB informático-geeks»).
Ampliación: Javi y Jorge nos enviaron un enlace a la definición de Mebibyte (MiB), una unidad de información/memoria que se definió en 1998 por la International Electrotechnical Commission (y apoyado por el IEEE), que es la que equivale a los 1024 × 1024 = 1.048.576 bytes de toda la vida, para distinguirlos de los «otros» megabytes en base 10 («un millón de bytes»). También existen Kibiytes, Gibibytes y el resto de la familia «bi».
