Compresión usando PI

Mayo 27, 2006 on 2:18 pm | In Bromas/juegos, Hacks, Realidad |

Todos sabemos que la compresión de archivos tiene un límite, esto es, no se puede comprimir un archivo ya comprimido debido a su aleatoriedad. Por la misma razón no se pueden comprimir archivos mp3 ni películas divx. ¿Seguro?
En The $5000 Compression Challenge se cuenta una ¿historia? de un reto donde se premia con 5000$ a la persona que consiga comprimir un archivo que se le facilita. Para que sea válido el fichero comprimido junto con su descompresor no deben ocupar más que el fichero en sí. En el link se cuenta como una persona consiguió ganar (aunque no se le consideró válido) metiendo información en el sistema de ficheros.

Pues yo tengo otro método que creo que sería válido, y este no me lo pueden rebatir.

Debido a la naturaleza del número PI y su aleatoriedad, se puede decir que cualquier número que busquemos lo podemos encontrar en alguna posición entre los decimales de PI. Si el número es muy grande tendremos que buscar entre más decimales, pero con paciencia, aparecerá.

En la página PI Phone Number Search Engine, tenemos una herramienta que nos busca una secuencia de 7 números en los decimales de PI. Pues bien, sólo necesitamos un buscador en los decimales de PI que nos permita buscar secuencias más largas, y cada vez que encontremos una secuencia que se pueda ubicar con menos datos que la longitud de la secuencia seleccionada ya hemos comprimido (y con paciencia se podrían encontrar secuencias muy muy largas). El descompresor sería tan simple como un programa que calcule los decimales de PI y se dedique a buscar las secuencias indicadas en el archivo comprimido.

¿Os parece viable? Por supuesto que como compresor usable no, debido al tiempo que tardaría, pero, ¿para ganar el premio? ¿Alguien lo implementa?

4 comentarios »

Suscripción RSS a los comentarios de la entrada. URI para TrackBack.

  1. jejeje, buen intento pero es matemáticamente incorrecto!!!!

    La codificación de la posición en la que aparece el archivo a comprimir en los decimales de PI ocuparía más bits que el propio archivo.
    Esto está demostrado matemáticamente, y es en realidad casi trivial, y además hay ya páginas web que desmontan esa teoría.
    El fallo me recuerda al fallo de la técnica de apostar cada vez el doble al rojo o al negro en la ruleta… parece funcionar pero falla escandalosamente cuando se echan los números o se piensa que ocurre en los casos medios y en los desfavorables.
    Sin acritud. :-)

    Comentario por carlosab — Sábado 27 Mayo, 2006 #

  2. No sé mucho sobre el tema, pero se me ocurre que el número de siete cifras 1234567 podría estar
    en la posición decimal XXXXXXXXXX de PI, así que no ganarías nada.

    Buscando en la página esa de los teléfonos:

    “The number 1234567 was found starting at position 9470344 to the right of the decimal point”

    que no es tan desfavorable como pensaba, pero no comprime nada.

    Comentario por hommer — Sábado 27 Mayo, 2006 #

  3. Habrá casos (muchos) en los que los bits usados para codificar la posición dentro de PI ocupen más que el fichero, y otros (muy pocos) en los que ocupen menos.

    Pero esto mismo es igual de válido para PI como para cualquier otro número irracional (E, por ejemplo). Es posible que justo tengas suerte y que la secuencia de bits se encuentre en una posición muy baja, lo que te daría una buena compresión, pero lo más probable es justo lo contrario.

    Si pruebas a introducir distintos números en el buscador de teléfonos, verás que la mayoría de las veces te devuelve posiciones con la misma cantidad de dígitos que la longitud del número buscado.

    Aún así, esta técnica tal vez se pudiese extender para crear un “buscador de algoritmos generadores de números irracionales” que se dedicase a encontrar el algoritmo concreto capaz de generar la secuencia de bits del fichero que queramos comprimir. El problema está en que tardaría un tiempo más bien cercano a infinito, y aún así tal vez ni lo consiguiese encontrar.

    Comentario por JarFil — Sábado 27 Mayo, 2006 #

  4. Hola chicos,
    no soy matematico y la fisica se me dio muy mal, pero si se ver.
    Veamos, lo ideal seria da una posicion que ocupe menos espacio de memoria que la real. Bueno eso seria comprir la informacion de la posicion para comprimir el documento.
    Bueno entoces creo que es factible si, yo dando la posicon en coordenadas con solo 4 digitos lo tenga, y la cadena entre mas larga mejor es decir no sea igual a cuatro o igual a los bits que ocupe su posicion.
    Pongamos una tabla cuadriculada de 10×10 o 100×100 mas grande entre mas grande sea la cadena buscada, solo necesito saber cuando empieza y cuando termina dicha cadena en un valor conocido en este caso pi. ej. empieza en cuadricula AB y termina en FI.
    Si no esta dentro de los primeros 100×100, hago otros 100×100 de los siguientes. Solo tengo que indicar cuantas veces lo he hecho para luego poderlo buscar. 3xABFI ej.
    Ademas ¿porque tiene que seguir la secuencia el orden de entrada? solo en colocar el orden de lectura podre leer la secuencia, es decir la que antes encuentre en pi.De alante atras o detras alante.

    Porque digo esto, sensillo 1234567 esta una posicion anterior a la que podria encontrar con 7654321, Es decir, a la hora de buscar busco dos parametros asi adelanto.Y por lo tanto si se diera el caso lo leeria asi, 2xFIAB.

    De todas formas, he observado que da un valor igual o superior al que busco cuando existe al final ceros. Y entre mas ceros peor es.
    1234000 posicion 20713054. Pero si sutituyo los ceros por unos, jeje 1234111 esta en la posicion 2032251 mismo numero de digitos, si este patron se repite siempre, sustituiria los ceros por unos al final de las colas.

    Tambien puede ser que haya tomado demasiado cafe y este diciendo cosas incoherentes. Pero ha sido divertido. Mejor que ver la tele.

    1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 0628620899 8628034825 3421170679 8214808651 3282306647 0938446095 5058223172 5359408128 4811174502 84102701936446229489 5493038196 4428810975 6659334461 2847564823 3786783165 2712019091 4564856692 3460348610 4543266482 1339360726 0249141273 7245870066 0631558817 4881520920 9628292540 9171536436 7892590360 0113305305 4882046652 1384146951 9415116094

    3305727036 5759591953 0921861173 8193261179 3105118548 0744623799 6274956735 1885752724 8912279381 8301194912 9833673362 4406566430 8602139494 6395224737 1907021798 6094370277 0539217176 2931767523 8467481846 7669405132 0005681271 4526356082 7785771342 7577896091 7363717872 1468440901 2249534301 4654958537 1050792279 6892589235 4201995611 2129021960 8640344181 5981362977 4771309960 5187072113 4999999837 2978049951 0597317328 1609631859 5024459455 3469083026 4252230825 3344685035 2619311881 7101000313 7838752886 5875332083 8142061717 7669147303 5982534904 2875546873 1159562863 8823537875 9375195778 1857780532 1712268066 1300192787 6611195909 2164201989

    El problema a todo esto es ej. si busco el numero 8521105 esta en la posicion 171 y segun lo que yo decia en una tabla ej 10×10 en la posicion 2×1577
    ocupo mas que la propia posicion, como decian antes. Pero si seria muy util si busco el numero 5011258 que es la posicion 10096114 y seria 2×7715
    aunque mas facil seria decir que es la posicion 171 opuesta.

    Lo dicho demasiado cafe.
    un saludo

    Comentario por uno cualquiera de este planeta — Sábado 6 Septiembre, 2008 #

Deje un comentario

XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <em> <i> <strike> <strong>

Powered by WordPress with Pool theme design by Borja Fernandez.
Entries and comments feeds. Valid XHTML and CSS. ^Top^