¿Cómo cambiaría el mundo si fuera posible comprimir 25GB de datos a 1.2MB en menos tiempo que ahora y usar los datos miles de veces más rápido que ahora?

Answer 1

Si yo fuera el creador de tal algoritmo, lo primero que haría sería averiguar qué otras leyes de la física y las matemáticas dejaron de funcionar. A la inversa, querré saber cómo salir de la matriz.

Aparte de eso, rápidamente me convertiré en el hombre más rico vivo vendiendo un servicio similar a netflix por una fracción del costo operativo, transmitiendo cualquier cosa a cualquiera en el planeta en Full HD con solo un grupo de servidores de bajo costo que tengo bajo mi escritorio.

Escribir un algoritmo que comprime grandes cantidades de datos no es nada emocionante. Aquí hay un algoritmo que funciona bien:

Entrada: 25 GB de solo la letra ‘A’
Algoritmo: Averigüe cuántas veces se repite una letra, escriba la letra, luego escriba cuántas veces se repite.
Salida: A26843545600
Relación de compresión: 99.9999999996%

La parte difícil son los datos de compresión que en realidad tienen información interesante. Si está hablando de compresión sin pérdida, existen limitaciones importantes sobre cuánto puede comprimir algo, esto se denomina “densidad de información” y es parte de una rama matemática llamada “teoría de la información”. La densidad de información del texto en inglés es de aproximadamente 1.75 bits por carácter. Eso significa que es * matemáticamente imposible * comprimir texto a más del 21% de su tamaño original sin perder información. Casualmente, esa cifra coincide con lo que puede obtener con los algoritmos modernos. Por “matemáticamente imposible” me refiero a algo como tener éxito en dibujar un triángulo con dos ángulos rectos en un plano, derivar una raíz racional de -1 o dividir por cero. No tiene sentido hablar de eso.

Para videos e imágenes puede tener una compresión con pérdida y luego es un juego de cuánta información del origen está dispuesto a perder. Por lo general, puede permitirse perder hasta un 95% de la información en bruto original y aún así obtener una imagen de aspecto decente. De lo que hablas está en el área 99.999952% de pérdida. Eso es 5 órdenes de magnitud más grande. A esa velocidad, podrá mantener solo 0,5 bits para cualquier fotograma de un video de 30 minutos. Eso no es suficiente para pintar todo el marco en blanco o negro. Realmente, no tiene sentido hablar de esas figuras, a menos que desee un video de un cuadro completamente negro que cambie a blanco unas cuantas veces por segundo.

Esto realmente suena como una idea terrible de una novela de ficción. Si algo así hubiera aparecido en los primeros capítulos de un libro que acabo de recoger, lo arrojaré a la papelera sin pensarlo dos veces. Muestra una falta muy básica de investigación por parte del autor sobre cómo funciona la computación en general y la teoría de la información en trabajos específicos. Tener el dispositivo principal de la trama de tu historia es algo que no tiene ningún sentido, es una enorme suspensión de incrédulos asesinos. Si confía en personas con conocimientos tecnológicos remotos como audiencia, es posible que desee reconsiderar esta opción.

Dicho dispositivo de trazado también es un “dispositivo del día del juicio final” omnipotente inmediato. No hay nada que no pueda hacer, y si los lectores lo piensan por un momento, no tiene sentido que tu héroe haga otra cosa que no sea convertirse en la persona más rica viva y conquistar el mundo.

Solo como referencia, si alguien tiene un algoritmo de este tipo, sería un poco mejor que probar que P = NP, lo que hace que todo cifrado sea trivialmente rompible. P = NP todavía es una posibilidad matemática, aunque remota, y hay algunas obras de ficción que profundizan en esta posibilidad.

Answer 2

Si este esquema de compresión es en realidad un 100% sin pérdidas, entonces realmente suena bastante interesante pero tiene un costo enorme, quizás imprevisto.

En este momento, todos nos estamos ahogando en grandes franjas de publicidad de videos no deseados … no solo en la televisión, sino en Internet, en tiendas de comestibles / grandes almacenes, en estaciones de servicio y en muchos otros lugares. Si el ancho de banda para la publicidad en video se reduce repentinamente a 1 / 25,000 de la corriente, todos deberíamos esperar ser sometidos a más publicidad de video no deseada de la que ahora sufrimos; virtualmente todos los anuncios “irían A / V” y ninguno de nosotros podría disfrutar de un simple silencio de audio / visual. Podríamos esperar “entretenimiento” (publicidad) de A / V de nuestros cabezales de ducha, nuestros inodoros, todo nuestro transporte público, todas las tiendas, muchas fachadas, la propia acera. Ningún sitio web estaría sin el molesto video grabado en toda la pantalla. También veríamos un aumento espectacular en el video de YouTube (y Vimeo, etc.), principalmente en “vides” y otros usos de importancia personal.

Usted, personalmente, puede ganar mucho dinero vendiendo este esquema de compresión a Adobe … y si el resto de nosotros descubriera que usted fue el único que hizo posible toda esa publicidad, es posible que alguna noche se encuentre de rodillas en un callejón oscuro. 8)

Answer 3

Por supuesto, usted comprende que no existe un algoritmo de compresión universal (uno que comprima todas las entradas por encima de un tamaño determinado). Pero como no te interesan las pruebas matemáticas, asumamos que tu algoritmo existe. En ese caso, no hay razón para detenerse con una relación de compresión de 20,000 a 1. Simplemente puede comprimir la salida de nuevo para lograr proporciones arbitrariamente altas. Eventualmente, podría comprimir toda la información del mundo en un archivo pequeño que podría imprimir en una sola hoja de papel si lo desea.

Una aplicación inmediata sería probar P = NP y reclamar el premio de USD $ 1 millón ofrecido por The Clay Mathematics Institute. El siguiente algoritmo responde a cualquier pregunta de sí / no en el tiempo O ( n ) (es decir, proporcional al tamaño de la entrada, n ), incluso cuando se haya demostrado que no existe ningún algoritmo, como el problema de detención. Suponemos que su algoritmo de compresión comprimirá todas las entradas mayores a m bits en al menos un bit. Los pasos son los siguientes:

1. Comprima recursivamente la entrada desde n bits hasta m bits en un máximo de n – m pasos.

2. Busque la respuesta en una tabla de 2 ^ m por 1 bit.

El paso 1 requiere a lo sumo n – m pasos de añadir al menos un bit de entrada y comprimir a m . Dado que estos pasos no dependen de n , toman tiempo constante. El Paso 2 también toma tiempo constante y supone que las respuestas a todas las preguntas posibles se han preparado con anticipación. (Dado que esta tabla tiene un tamaño finito, esta tarea podría completarse en tiempo finito). Por lo tanto, todo el algoritmo se ejecuta en tiempo O ( n ).

Es posible que le preocupe que si m es más grande que alrededor de 30 o 40, entonces la tabla sería demasiado grande para una implementación práctica. No es para preocuparse. Primero, el Instituto Clay solo necesita una prueba matemática, que usted haya satisfecho. En segundo lugar, puede utilizar su algoritmo de compresión para comprimir una tabla arbitrariamente grande hasta m bits. Como beneficio adicional, su algoritmo de compresión permite leer la tabla sin descomprimirla.

Me imagino que un oráculo universal podría ser bastante útil. Podría ampliarlo para responder preguntas con respuestas arbitrariamente largas utilizando una tabla que arroje la respuesta comprimida recursivamente. Puede usar este método para resolver los 5 problemas restantes de Clay Millennium, que valen $ 1 millón cada uno. (La conjetura de Poincare ya ha sido reivindicada).

---

Answer 4

Es extremadamente improbable que algún dato real sea tan comprimible. La compresión se basa en la duplicación de información.

La compresión sin pérdida (muy simplificada) reemplaza las secuencias duplicadas con un código de identificación más corto. Por ejemplo, “la nueva identificación del álbum de Duran Duran llamada los mejores éxitos de Duran Duran” se puede reemplazar por “1 = Duran: la nueva identificación del álbum de 1 1 llamada los mejores éxitos de 1 1” con un ahorro de 8 caracteres, pero la compresión sin pérdidas no está garantizada para hacer un archivo más pequeño. Si lo fuera, podría volver a comprimir el archivo comprimido hasta que se redujera a 1 byte, ¡representando todos los archivos posibles!

Cualquier forma de compresión “con pérdida” pierde parte de la distinción entre diferentes estados de datos, por lo general, descartar la información que no se considera importante, y esto ya se ha hecho en DVD / BluRays; es poco probable que mejoremos.

Answer 5

Esto no tiene ningún sentido.

cualquier algoritmo de compresión sin pérdida siempre dará como resultado que algunos archivos sean más comprimidos que no comprimidos. Para dar una prueba simple: dado que las películas son solo colecciones de datos, si su algoritmo siempre puede dar como resultado una reducción en el tamaño del archivo, entonces es posible aplicar el algoritmo de forma recursiva hasta que el tamaño del archivo alcance 0, lo que es absurdo.