¿Se pueden usar los PRNG para comprimir mágicamente cosas?

38

Esta idea se me ocurrió cuando era un niño aprendiendo a programar y en el primer encuentro con PRNG. Todavía no sé cuán realista es, pero ahora hay intercambio de pila.

Aquí hay un esquema de 14 años para un sorprendente algoritmo de compresión:

Tome un PRNG y siembre con semilla spara obtener una secuencia larga de bytes pseudoaleatorios. Para transmitir esa secuencia a otra parte, solo necesita comunicar una descripción del PRNG, la semilla apropiada y la longitud del mensaje. Para una secuencia lo suficientemente larga, esa descripción sería mucho más corta que la secuencia misma.

Ahora supongamos que puedo invertir el proceso. Con suficiente tiempo y recursos computacionales, podría hacer una búsqueda de fuerza bruta y encontrar una semilla (y PRNG, o en otras palabras: un programa) que produzca mi secuencia deseada (Digamos que una foto divertida de gatos siendo traviesos).

Los PRNG se repiten después de que se haya generado un número suficientemente grande de bits, pero en comparación con los ciclos "típicos", mi mensaje es bastante corto, por lo que esto no parece ser un gran problema.

Voila, una forma efectiva (aunque rube-Goldbergian) de comprimir datos.

Entonces, suponiendo:

  • La secuencia que deseo comprimir es finita y conocida de antemano.
  • No tengo poco efectivo ni tiempo (siempre y cuando se requiera una cantidad finita de ambos)

Me gustaría saber:

  • ¿Existe un defecto fundamental en el razonamiento detrás del esquema?
  • ¿Cuál es la forma estándar de analizar este tipo de experimentos mentales?

Resumen

A menudo, las buenas respuestas dejan en claro no solo la respuesta, sino qué es lo que realmente estaba preguntando. Gracias por la paciencia de todos y las respuestas detalladas.

Aquí está mi enésimo intento de un resumen de las respuestas:

  • El ángulo PRNG / seed no aporta nada, no es más que un programa que produce la secuencia deseada como salida.
  • El principio del casillero: hay muchos más mensajes de longitud> k que programas de generación de mensajes <= k. Entonces, algunas secuencias simplemente no pueden ser la salida de un programa más corto que el mensaje.
  • Vale la pena mencionar que el intérprete del programa (mensaje) está necesariamente arreglado de antemano. Y su diseño determina el subconjunto (pequeño) de mensajes que se pueden generar cuando se recibe un mensaje de longitud k.

En este punto, la idea original de PRNG ya está muerta, pero hay al menos una última pregunta que resolver:

  • P: ¿Podría tener suerte y descubrir que mi mensaje largo (pero finito) resulta ser la salida de un programa de longitud <k bits?

Estrictamente hablando, no es una cuestión de casualidad ya que el significado de cada mensaje (programa) posible debe conocerse de antemano. O es el significado de algún mensaje de <k bits o no lo es .

Si elijo un mensaje aleatorio de> = k bits aleatoriamente (¿por qué lo haría?), En cualquier caso, tendría una probabilidad de desaparecer de poder enviarlo con menos de k bits, y una certeza de no poder enviar en absoluto utilizando menos de k bits.

OTOH, si elijo un mensaje específico de> = k bits de aquellos que son la salida de un programa de menos de k bits (suponiendo que exista tal mensaje), entonces, en efecto, estoy aprovechando los bits ya transmitidos al receptor (el diseño del intérprete), que cuenta como parte del mensaje transferido.

Finalmente:

En última instancia, ambos nos dicen lo mismo que el principio de casillero (más simple) nos dice cuánto podemos comprimir: quizás nada, tal vez algo, pero ciertamente no tanto como imaginamos (a menos que hagamos trampa).

DW
fuente
66
Ajusta un poco tu pregunta y aún no puedes comprimir cada cadena (como se describe en las respuestas a continuación), pero obtienes la Teoría de información algorítmica ( en.wikipedia.org/wiki/Kolmogorov_complexity ). Reemplace "PRNG" con "máquina universal de Turing" y "seed" con "cinta de entrada que contiene un programa que genera la salida que quiero". La mayoría de las cintas de entrada son más largas que las salidas que generan, pero para cada salida existe al menos una entrada que genera esa salida.
Wandering Logic
No, pero el tamaño comprimido es la entropía de la fuente ^ _ ^
Navin
55
Si realmente implementa esto, encontrará algo interesante: para reconstruir la entrada arbitraria, necesitará un seed + rng que es, en promedio, tan grande como los datos originales. Ups
Marcar
Otra forma de entender por qué esto no funcionará: aunque un PRNG puede generar resultados arbitrariamente largos , no puede generar resultados arbitrarios . (La salida de un PRNG siempre será un ciclo o patrón fijo, limitado por el tamaño de su estado.)
Pi Delport
@PietDelport, para cualquier n hay un PRNG cuyo ciclo es mucho más grande, y la pregunta planteada no se conoce de antemano. Por lo tanto, no estoy convencido de que el hecho de que los PRNG sean cíclicos en sí resuelvan directamente la cuestión.

Respuestas:

43

Tienes un nuevo esquema de compresión brillante, ¿eh? Muy bien, entonces ...

♫ Juguemos todos, el juego de entropía ♫

Para ser simple, supondré que desea comprimir mensajes de exactamente bits, para algunos n fijos . Sin embargo, desea poder usarlo para mensajes más largos, por lo que necesita alguna forma de diferenciar su primer mensaje del segundo (no puede ser ambiguo lo que ha comprimido).nn

Entonces, su esquema es determinar alguna familia de PRNG / semillas de tal manera que si desea comprimir, digamos, , simplemente escriba algún número k , que identifica algún combo de semillas / PRNG precomputado (y compartido) que genera esos bits después n consultas. Bien. ¿Cuántas cadenas de bits diferentes de longitud n hay? 2 n (tiene n opciones entre dos elementos; 0 y 1 ). Eso significa que tendrás que calcular 2 n de estos combos. No hay problema. Sin embargo, necesitas escribir k en binario para que yo pueda leerlo. ¿Qué tan grande puede ser k ? Bueno, puede ser tan grande como 201000111001knn2n012nkk . ¿Cuántos bits necesito para escribir 2 n ? log 2 n = n .2n2nlog2n=n

¡Uy! ¡Su esquema de compresión necesita mensajes siempre y cuando esté comprimiendo!

"¡Jaja!", Dices, "¡pero ese es el peor de los casos! ¡Uno de mis mensajes se asignará a , que solo necesita 1 bit para representar! ¡Victoria!"01

Sí, ¡pero sus mensajes deben ser inequívocos! ¿Cómo puedo distinguir seguido de 0 de 10 ? Dado que algunas de sus claves son de longitud n , todas deben ser, o de lo contrario no puedo decir dónde comenzó y se detuvo.1010n

"¡Jaja!", Dices, "¡pero puedo poner la longitud de la cadena en binario primero! ¡Eso solo necesita contar a , que puede representarse por log n bits! Así que mi 0 ahora viene prefijado con solo log n bits, sigo ganando! "nlogn0logn

Sí, pero ahora esos números realmente grandes tienen el prefijo bits. ¡Su esquema de compresión ha hecho que algunos de sus mensajes sean aún más largos! Y la mitad de todos sus números comienzan con 1 , ¡así que la mitad de sus mensajes son mucho más largos!logn1

Luego procedes a arrojar más ideas, como un carácter de terminación, comprimir el número y comprimir la longitud en sí, pero todos estos se encuentran con casos en los que el mensaje resultante es más largo. De hecho, por cada bit que guarde en algún mensaje, otro mensaje se alargará en respuesta. En general, solo va a cambiar el "costo" de sus mensajes. Hacer algunos más cortos solo hará que otros sean más largos. Realmente no puede caber mensajes diferentes en menos espacio que escribir 2 n cadenas binarias de longitud n .2n2nn

"¡Jaja!", Dices, "¡pero puedo elegir algunos mensajes como 'estúpidos' y hacerlos ilegales! ¡Entonces no necesito contar hasta , porque no soporto tantos mensajes!"2n

Tienes razón, pero realmente no has ganado. Acaba de reducir el conjunto de mensajes que admite. Si sólo se admite y b = 111111110101000 como los mensajes que envía, entonces definitivamente puede simplemente tener el código de un 0 , b 1 , que coincide exactamente con lo que he dicho. Aquí, n = 1 . La longitud real de los mensajes no es importante, es cuántos hay.a=0000000011010b=111111110101000a0b1n=1

"¡Jaja!", Dices, "¡pero puedo simplemente determinar que esos estúpidos mensajes son raros! ¡Haré que los raros sean grandes y los comunes pequeños! ¡Entonces gano en promedio!"

¡Sí! ¡Felicitaciones, acabas de descubrir la entropía ! Si tiene mensajes, donde el i- ésimo mensaje tiene probabilidad p i de ser enviado, puede obtener la longitud esperada de su mensaje hasta la entropía H = n i = 1 p i log ( 1 / p i ) de este conjunto de mensajes Esa es una especie de expresión extraña, pero todo lo que realmente necesita saber es que es más grande cuando todos los mensajes son igualmente probables, y más pequeño cuando algunos son más comunes que otros. En el extremo, si sabes básicamente que cada mensaje será unnipiH=i=1npilog(1/pi) . Entonces puede usar este código súper eficiente: a 0 , x 1 x de lo contrario. Luego, su longitud de mensaje esperado es básicamente 1 , que es impresionante, y que va a estar muy cerca de la entropía H . Sin embargo, H es un límite inferior, y realmente no puedes vencerlo, no importa cuánto lo intentes.a=000111010101a0x1x1HH

Cualquier cosa que afirme vencer a la entropía probablemente no esté dando suficiente información para recuperar sin ambigüedad el mensaje comprimido, o simplemente está mal. La entropía es un concepto tan poderoso que podemos limitar el tiempo de ejecución de algunos algoritmos con límite inferior (y a veces incluso superior ), porque si se ejecutan muy rápido (o muy lento), entonces deben estar haciendo algo que viole la entropía .

Alexis Beingessner
fuente
13
Chico, ¿sueno tonto cuando finges ser yo? Gracias a Dios, puedo estar orgulloso de haber descubierto la entropía. Bromas aparte, esta es una buena respuesta: si solo el tono no estuviera tan teñido de burla.
66
No tenía la intención de burlarme, solo jugaba con la idea del "esquema de un niño de 14 años para un algoritmo de compresión sorprendente". :)
Alexis Beingessner
3
A mí tampoco me pareció una burla :) Este es un esquema bastante común para explicar problemas en la ciencia popular (y algunos otros campos), aunque es cierto que el "autor de la pregunta" suele ser Alice o Bob en lugar de un "verdadero" persona: D ¡Vea cuán fácilmente puede comprender de repente cuán complejo es realmente el problema! (sin mencionar que cuando estoy pensando en un tema complejo en mi cabeza, utilizo el mismo proceso: un diálogo interno es increíblemente bueno para simular "más cabezas saben más")
Luaan
2
@SteveJessop, esa es una dicotomía falsa y no vayamos allí. Es una buena respuesta y quizás soy demasiado sensible, eso es todo.
3
@chipmonkey, creo que todavía está cubierto por la respuesta de alexis sobre el "juego de entropía". Posiblemente, la cantidad de algoritmos necesarios para hacerlo sería tan grande que la cantidad de bits necesarios para especificar cuál se usaría cancelaría el beneficio.
21

Hay cadenas binarias de longitud inferior a N y 2 N cadenas binarias de longitud exactamente N . Esto significa que cualquiera que sea ​​su algoritmo de compresión , debe haber alguna cadena que no pueda comprimir en absoluto, solo porque la asignación de la cadena original a la cadena comprimida debe ser inyectiva (uno a uno). Esta es la fuerza impulsora detrás de muchas aplicaciones de la complejidad de Kolmogorov.2N1N2NN

En la vida real, a menudo sabemos algo sobre la secuencia que estamos comprimiendo, digamos que es voz o una imagen. En el caso de la compresión sin pérdidas, el teorema de codificación de fuente de Shannon muestra que la tasa de compresión óptima es igual a la entropía de la fuente. Para la codificación con pérdida hay otros teoremas en la teoría de la información (teoría de la tasa de distorsión). Entonces, incluso en este caso, hay un límite para la cantidad de datos que se pueden comprimir.

Yuval Filmus
fuente
Nunca lo he visto de esta manera, pero esto simplemente se me ocurrió: básicamente, Shannon dice que incluso el mejor de los casos no se puede comprimir arbitrariamente y el Principio de Pigeonhole garantiza que debe haber un peor de los casos que no se puede comprimir. en absoluto. ¿Es esa una caracterización sensata?
Jörg W Mittag
1
El mejor caso siempre se puede comprimir, ya que puede incluir alguna cadena como un caso especial de su algoritmo de compresión. Este argumento funciona no solo para el peor de los casos, sino también para el caso promedio, que muestra que la compresión promedio es como máximo de 2 bits.
Yuval Filmus
Ah, por supuesto. if input.empty? then output_very_long_stringdaría una relación de compresión infinita como el mejor caso. En realidad, incluso hay un algoritmo de compresión que usa esto. (Se me olvidó el nombre, por desgracia.) Está destinado a cadenas muy cortas, y tiene codificaciones especiales para subcadenas no modificables como http://, www., .comy así sucesivamente.
Jörg W Mittag
¿Puedo superar este argumento si tengo una manera de diseñar una familia PRNG de manera que las secuencias que no pueden expresar sean las que excluyo de antemano? (Me viene a la mente el ruido).
3
@ foo1899, si puede determinar que algunas cadenas son más probables que otras, entonces puede hacerlo mejor en promedio, sí. En general, el límite inferior es que el tamaño de mensaje comprimido esperado no puede superar . Donde p i es la probabilidad de que se envíe el i-ésimo mensaje posible. H es máximo cuando todos los mensajes son igualmente probables, y más pequeño de lo contrario. En el extremo, puede obtener un rendimiento promedio excelente si casi todos los mensajes son "hola", y cualquier otro mensaje es raro. Simplemente configure "hola" -> 0, y x-> 1x de lo contrario. H=ipilog1/pipiH
Alexis Beingessner
7

Imagine que su semilla tiene longitud k . Su PRNG es una función determinista de la semilla, por lo que produce como máximo 2 k secuencias diferentes de longitud n . Hay 2 n de estos, por lo que su esquema no funcionará a menos que se vuelva a enviar solo la cadena de n bits completa cuando no hay s correspondientes .sk2kn2nns

(Como señaló otra respuesta, esto sucederá para cualquier función de compresión que elija).

Louis
fuente
En sí mismo, eso no prueba que no pueda construir un PRNG que simplemente genere mi secuencia elegida como una de sus posibles salidas, a la vez que requiera muchos menos bits para hacerlo. Como entiendo por las otras respuestas, la entropía probablemente impone un límite inferior en el número de bits requeridos. Es decir, simplemente no puedo hacerlo arbitrariamente bien para mi secuencia elegida.
Todo esto dice es que si haces tu PRNG favorito, entonces yo puedo venir a usted con una secuencia que no produce, que ya rompe su idea. Una afirmación más fuerte es que hay secuencias que no son emitidas por ningún programa mucho más corto. (En otras palabras, aún pierdes incluso si te dejo cambiar tu función después de ver mi secuencia. Eso es a lo que Yuval alude con la "complejidad de Kolmogorov".)
Louis
4

Además de otros puntos ya compartidos, solo quiero agregar este enlace: https://www.schneier.com:443/blog/archives/2009/09/the_doghouse_cr.html

Ahora, la producción de energía anual de nuestro sol es de aproximadamente 1.21 × 10 ^ 41 ergios. Esto es suficiente para generar aproximadamente 2.7 × 10 ^ 56 cambios de un solo bit en nuestra computadora ideal; suficientes cambios de estado para poner un contador de 187 bits a través de todos sus valores. Si construimos una esfera Dyson alrededor del sol y capturamos toda su energía durante 32 años, sin ninguna pérdida, podríamos alimentar una computadora para contar hasta 2 ^ 192. Por supuesto, no le quedaría energía para realizar cálculos útiles con este contador.

Por lo tanto, solo iterar (sin comparar ...) para encontrar una constelación válida de 187 bits de sus datos deseados llevaría a condiciones ideales (no alcanzables) más energía de la que emite el sol durante un año.

usuario1186178
fuente
1

Una prueba muy rápida de que un compresor universal no puede existir. Supongamos que haces uno y comprimes una entrada. Ahora, comprime iterativamente la salida de tu programa. Si siempre puede reducir el tamaño, se hará cada vez más pequeño en cada paso, hasta que baje a 1 bit.

Podría argumentar que, tal vez, la salida de su algoritmo tiene una estructura tal que no se puede comprimir más, pero luego podría aplicar una combinación aleatoria * antes de volver a comprimir.

Nota a pie de página: Algunos cambios deterministas realmente ayudan en algunos esquemas de compresión: http://pytables.github.io/usersguide/optimization.html?highlight=shuffling#shufflingoptim

Davidmh
fuente
Creo que te falta que cada mensaje comprimido tenga una semilla sasociada. El mensaje 01001011 con un ´s´ de 2348 diferirá del mismo mensaje con un ´s´ de 3924. A menos que yo mismo haya entendido mal el algoritmo de foo1899.
Azeirah
1

El uso de un PRNG para "compresión" es básicamente útil en una situación: cuando es necesario usar un grupo de datos "aleatorio" y registrar de forma compacta qué datos se usaron. La mayoría de los generadores pseudoaleatorios solo pueden generar una pequeña fracción de secuencias posibles, pero si uno solo necesita un número pequeño a moderado de secuencias "aleatorias", la fracción de secuencias posibles que puede generar un PRNG a menudo será más que adecuada.

Si la secuencia de datos que se desea almacenar coincide casualmente con lo que generaría un determinado PRNG dada la semilla correcta, el almacenamiento de la semilla puede ser una alternativa compacta para almacenar los datos. Sin embargo, a menos que la fuente de datos sea tal que tales coincidencias puedan ocurrir, serían tan infrecuentes que no valdría la pena buscarlos.

Super gato
fuente
Los PRNG se utilizan de esta manera para representar de forma compacta (pseudo) datos aleatorios, por ejemplo, en aras de la repetibilidad de los experimentos.
Yuval Filmus
1
@YuvalFilmus: Exactamente. También se pueden usar en algunas situaciones, como la generación de niveles de videojuegos, donde una pequeña fracción de los niveles generados se consideraría aceptable, pero donde un diseñador de videojuegos puede generar niveles al azar hasta que encuentre algunos que sean de su agrado, y registrar las semillas que generó esos. Un concepto muy útil históricamente, cuando se codifica una máquina de videojuegos con 128 bytes de RAM, tratando de encajar el programa en un cartucho con 4096 bytes de ROM.
supercat
Es un muy buen ejemplo, coincide con el esquema que describí de buscar una semilla "buena", pero aprovecha el hecho de que en ese escenario muchos mensajes posibles son buenos.
@ foo1899: Por cierto, el juego "Pitfall" en.wikipedia.org/wiki/Pitfall ! utilizó la técnica mencionada anteriormente para generar un mapa de 256 pantallas en un cartucho de juego 4K en una máquina con 128 bytes de RAM.
supercat
1

Algo a considerar para agregar a la cacofonía de respuestas que afirman por qué hay algunas cadenas que no se pueden comprimir debido a la naturaleza inyectiva de la descompresión, por definición, y al universo limitado de cadenas comprimidas para seleccionar para representar los mensajes: la mayoría de las cadenas no se pueden comprimir porque hay muchas más cadenas de alta entropía desordenada que de baja entropía y estructuradas, lo que da lugar a la condición que vemos en la práctica que: la compresión es la mayor parte del tiempo útil, ya que los mensajes Los que más a menudo desean comprimir son aquellos que a menudo poseen una parte alícuota de orden y estructura, y por este motivo, son parte del universo mucho más pequeño de objetos de entropía inferior. Esto significa que es posible que, al elegir una longitud de salida adecuada, Podemos comprimir todo en el universo más pequeño y estructurado. El término estructurado, entropía y ordenado aquí es deliberadamente impreciso, para reflejar las definiciones subjetivas de la semántica y la utilidad de los mensajes que deseamos comprimir.

Y en respuesta directa a la solicitud del interlocutor: * sí, por supuesto, podrías tener suerte y encontrar que la salida de tu PRNG es el mensaje exacto que deseas comprimir, es solo que a menudo no encontrarás este es el caso porque La propiedad misma que caracteriza a un PRNG, es decir, su capacidad para producir una variedad (casi) interminable de cadenas diferentes, hace que sea poco probable que produzca el suyo.

Por supuesto, podría mitigar esta probabilidad utilizando un PRNG para recorrer un "gráfico de dominio" de las transiciones de palabra a palabra, y aumentará enormemente la probabilidad de la aparición de su mensaje, y también encontrará que ahora debe agregar el gráfico de dominio al mensaje comprimido longitud.

Cris
fuente