Matemático de la U. de Chile descubre nuevo límite en la compresión de datos gracias a la magia

El mago le da una baraja de naipes a un voluntario del público. Le pide que corte y luego saque 6 cartas y -sin mostrarlas- vaya nombrando sus colores en orden. Ante el asombro del voluntario, y de la audiencia, el mago puede decirle exactamente cuáles son las 6 cartas que acaba de sacar.

Ese truco fue publicado en una revista cualquiera y un alumno de la Universidad de Chile se basó en él para hacer un importante descubrimiento. Travis Gagie, quien por estos días trabaja en la Universidad de Atto en Finlandia, nos cuenta que leyó sobre el truco de cartas justo en un momento de su carrera en que conducía una investigación ligeramente emparentada con el artículo leído.

Un par de vueltas al asunto y las neuronas hicieron sinapsis: era posible aplicar sus conclusiones a los algoritmos de compresión teóricos.

Pero no nos adelantemos a los hechos. ¿Cómo sabe el mago cuáles son las cartas? La clave es arreglar el mazo previamente en una secuencia de colores que sigue un patrón específico, llamado secuencia de De Bruijn. Esta secuencia sigue un alfabeto en el que cada posible subsecuencia de 6 naipes aparece una sola vez.

Si el mazo de cartas está ordenado de esta forma y el mago ha memorizado el ciclo De Bruijn, ya conoce todos los posibles sextetos que pueden formarse con seis cartas consecutivas. (El problema es memorizar todas las posibles secuencias, claro, y que el voluntario corte el mazo en vez de barajarlo). Considerando que el mago no es adivino, obviamente hay un truco de por medio y se los acabamos de revelar.

Cuando Travis Gagie leyó sobre ese truco, se encontraba en medio de una investigación que giraba en torno a la entropía empírica. En particular, habían concluído que una manera de establecer el orden kesimo de entropía de una secuencia era igualarlo al grado de incertidumbre de un elemento cualquiera de esa secuencia dado que se conociera previamente los primeros k elementos de ésta. Pues bien, cuando leyó aquel artículo dijo:

Pero si esto es obvio! 1 La entropía empírica de cualquier sexteto en un conjunto de Bruijn de kesimo orden es cero!

La meditación acerca del comportamiento de los ciclos de Bruijn en combinación con sus propias investigaciones sobre la entropía empírica, lo llevó a simular variaciones en donde se trabaja con una baraja no arreglada previamente, y sacando siete cartas en vez de seis. El voluntario ha de volver a meter las cartas en el mazo, y acto seguido lo cortará. El desafío es “adivinar” cuáles eran esas 7 cartas. Dice Gagie:

“No es difícil 2 demostrar que la probabilidad de que dos séptuplos de cartas tengan los mismos colores en el mismo orden es a lo más 1/128″

Analizando el problema, y modificando la cantidad de cartas a sacar en cada muestra, o las características de la baraja (que en realidad representa cualquier conjunto finito), le permitieron a Travis Gagie publicar un paper que encontrarán al pie de este artículo.

En él, se establecen cuatro teoremas que plantean la probabilística de deducir correctamente el valor de una serie de elementos extrayéndolos de un universo dadas una serie de condiciones. En ellos, se utiliza la combinación entre el truco de magia y la investigación de Gagie para establecer un límite teórico aplicable a la compresión de datos, y cuya particularidad es que establece -dentro del plano de lo matemáticamente posible- un radio de compresión teóricamente posible más bajo que cualquiera que haya sido demostrado anteriormente. Sin embargo, Travis no encuentra que su investigación sea para celebrar:

Es más bien un descubrimiento negativo. Demuestra que no es posible hacer ciertas cosas con algoritmos de compresión

El hecho de descubrir un límite (aunque sea más bajo que los que se conocían antes) sigue significando que ese límite acota las posibilidades de los algoritmos de compresión, pero eso no quita que empujar el límite teórico un poco más allá sea un progreso. Vale la pena mencionar que esto no significa que WinRAR mañana vaya a comprimir más rápido o mejor, pero sí es cierto que los algoritmos que hoy se usan en esa clase de aplicaciones una vez no fueron más que tiza sobre un pizarrón, e ideas en la cabeza de alguien tan brillante como Travis Gagie.

Además, no todos los días un truco de magia inspira cuatro teoremas matemáticos.

Artículo original