Reducir el tiempo de descarga usando números primos

La compresión universal sin pérdidas es imposible, esto no puede funcionar. El conjunto de cadenas binarias de longitud$n$no es inyectiva al conjunto de cadenas binarias de longitud$n-1$.

Hay$2^{n}$cadenas binarias de longitud$n$. Llamemos al conjunto de todas las cadenas binarias de longitud dada$S_{k}$. Cuando$k=n-1$, hay$|S_{n-1}| = 1+2+2^{2}...+2^{n-1}=2^{n}-1$

Desde$2^{n} > |S_{n-1}|$, el principio del casillero implica que no existe una función inyectiva del conjunto de todas las cadenas binarias de longitud$n$a cualquier$S_{k}$para$k<n$. Esto significa que un esquema perfecto de compresión sin pérdidas como el descrito es imposible ya que constituiría tal función.

Además, para cualquier número$n$existe una cadena de longitud$n$cuya complejidad Kolmogorov-Chaitin es$n$.

Si asume que este no es el caso, tiene alguna función$g:P \to X$dónde$p_{x} \in P$es un programa que codifica una cadena$x \in X$cuya complejidad$C(x)<|x|$. tal que$g(p_{x})=x$y$|p_{x}|< |x|$. También sabemos que$x \neq y \implies p_{x} \neq p_{y}$. De nuevo por el principio del casillero si todos$2^{n}$cadenas de longitud$n$tener un programa cuya longitud es menor que$n$, de los cuales sólo puede haber$2^{n}-1$, debe haber un programa que produzca dos cadenas diferentes, de lo contrario, el conjunto más grande no está cubierto. Nuevamente, esto es absurdo, por lo que al menos una de estas cadenas tiene una complejidad de al menos su propia longitud.

Editar:A las preguntas sobre la compresión con pérdida, parece poco probable que este esquema sea ideal para la gran mayoría de los casos. No tiene forma de controlar dónde y cómo induce errores. Los esquemas de compresión como H.264 aprovechan la estructura visual inherente de una imagen para lograr una mejor fidelidad en tamaños más bajos. El método propuesto elegiría indiscriminadamente una solución para el sistema de ecuaciones que genera, lo que probablemente introduciría artefactos notables. Creo que también es posible que estos sistemas estén sobredeterminados, usando espacio innecesario, mientras que una DCT es una descomposición ortogonal. La solución de estas ecuaciones probablemente también tendría que encontrarse usando un solucionador SAT/SMT, cuyo tiempo de ejecución también haría que la descompresión muy costoso si no intratable, mientras que las técnicas basadas en DCT están bien estudiadas y optimizadas para el rendimiento,

Todo el crédito por una excelente pregunta en la que ha gastado mucha energía creativa. Este es un comentario en lugar de una respuesta porque es demasiado largo para el cuadro de comentarios habitual.

Tiene una idea interesante y continúe investigándola, pero ¿sabía que la compresión de datos ya tiene una base de investigación muy amplia? Es posible que desee investigar en caso de que su idea, o algo similar, ya esté disponible. Hay un artículo de Wikipedia sobre la compresión como punto de entrada al tema.

Algunas observaciones son:

1. Los archivos de sonido, películas e imágenes utilizados por la mayoría de las aplicaciones están altamente comprimidos, generalmente (pero no siempre) utilizando algoritmos imperfectos con una pérdida de datos asociada. Formatos como zip, jpeg, mp3, mov e incluso png, por lo tanto, no están 'listos para funcionar al recibirlos', pero a veces necesitan un procesamiento extenso antes de su uso. Los algoritmos se han desarrollado mucho en los últimos 50 años y, en algunos casos, son muy sofisticados.

2. En general, la compresión explota la regularidad en los datos originales (como una foto, donde gran parte de la imagen puede ser similar, o texto donde el mensaje puede usar solo una pequeña cantidad de palabras diferentes) y funciona peor o no funciona en absoluto cuando el archivo los datos son verdaderamente aleatorios.

3. En algunas aplicaciones, la pérdida de datos puede ser aceptable, por ejemplo, en una imagen o música donde el ojo o el oído realmente no pueden ver ni escuchar pequeñas imperfecciones, y en estos casos se pueden obtener niveles muy altos de compresión (por ejemplo, una reducción del 90 % en el tamaño ). Pero para muchos propósitos, necesita resultados perfectos garantizados, ya que la pérdida de precisión simplemente no será aceptable, por ejemplo, en un archivo de programa de computadora o en un texto. Los datos a menudo todavía se pueden comprimir, aprovechando la regularidad existente, pero no se garantiza un ahorro en todos los casos.

Un comentario final sobre estas observaciones es que aplicar la compresión dos veces rara vez es efectivo porque los datos regulares una vez comprimidos se vuelven mucho menos regulares y menos susceptibles a una mayor compresión, por lo que tratar de comprimir un archivo jpg o mp3 generalmente no ahorrará nada e incluso puede costar espacio. .

Comenzaré confesando que no leí la descripción completa de su esquema de compresión en detalle. Realmente no necesito hacerlo, ya que lo que está tratando de lograr es un esquema de compresión de datos sin pérdidas independiente de la entrada, y eso es imposible.

Teorema 1: no existe un esquema de compresión sin pérdidas que mapee cada archivo de longitud$n$bits a un archivo de longitud inferior a$n$pedacitos

La prueba se sigue fácilmente del principio del casillero y del hecho de que hay$2^n$archivos distintos de$n$pedacitos pero solo$2^n-1$archivos distintos de menos de$n$pedacitos Esto implica que cualquier mapeo de esquema de compresión$n$-archivos de bits a archivos de menos de eso$n$Los bits deben asignar al menos dos archivos de entrada al mismo archivo de salida y, por lo tanto, no pueden tener pérdidas.

Teorema 2: No existe un esquema de compresión sin pérdidas para el cual la longitud promedio de los archivos de salida sea más corta que la longitud promedio de los archivos de entrada (con promedios tomados de todos los archivos de entrada posibles como máximo).$n$bits de longitud, para cualquier entero no negativo$n$).

Este teorema más fuerte es un poco más complicado de probar. Para ser breve, supondré que está familiarizado con la notación básica de la teoría de conjuntos, como$R \cup S$por la unión,$R \cap S$para la intersección y$R \setminus S = \{x \in R : x \notin S\}$por la diferencia de los conjuntos$R$y$S$.

Necesitamos un poco de notación adicional. Específicamente, deja$\operatorname{len}(x)$indicar la longitud del archivo$x$, y deja$\operatorname{len}(S) = \sum_{x \in S} \operatorname{len}(x)$denota la longitud total sumada de todos los archivos en el conjunto$S$. Así, la longitud media de los archivos en$S$es$\frac{\operatorname{len}(S)}{|S|}$, dónde$|S|$es el número de archivos en$S$. También$\operatorname{len}(R \cup S) = \operatorname{len}(R) + \operatorname{len}(S)$para dos conjuntos disjuntos de archivos$R$y$S$.

Ahora deja$f$ser un esquema de compresión sin pérdidas, es decir, una función de asignación de archivos a archivos, vamos$A$ser el conjunto de todos los archivos de longitud máxima$n$pedacitos, y dejar$B = \{f(x) : x \in A\}$Sea el conjunto de archivos obtenidos aplicando$f$a cada archivo en$A$. Desde$f$no tiene pérdidas, debe mapear cada archivo de entrada en$A$a un archivo de salida distinto; de este modo$|B| = |A|$, y así también$|A \setminus B| = |B \setminus A|$.

Desde$A$es el conjunto de todos los archivos como máximo$n$bits de largo, se sigue que$\operatorname{len}(x) ≤ n$si y solo si$x \in A$. De este modo

$$\operatorname{len}(A \setminus B) ≤ n \cdot |A \setminus B| = n \cdot |B \setminus A| ≤ \operatorname{len}(B \setminus A)$$ (donde la segunda desigualdad es estricta a menos que$A = B$, lo que implica que$A \setminus B = B \setminus A = \emptyset$).

Además, desde$A \cap B$es disjunto de ambos$A \setminus B$y$B \setminus A$,

$$\begin{aligned}\operatorname{len}(A) &= \operatorname{len}(A \cap B) + \operatorname{len}(A \setminus B) \\ &≤ \operatorname{len}(A \cap B) + \operatorname{len}(B \setminus A) \\ &= \operatorname{len}(B).\end{aligned}$$ Y desde$|A| = |B|$, como se señaló anteriormente, por lo tanto tenemos$\frac{\operatorname{len}(A)}{|A|} ≤ \frac{\operatorname{len}(B)}{|B|}$(donde, de nuevo, la desigualdad es estricta a menos que$A = B$).

---

PD. Entonces, ¿cómo funcionan los esquemas de compresión sin pérdidas del mundo real ? En pocas palabras, se basan en el hecho de que la mayoría de los archivos "naturales" (que contienen datos de imagen o sonido sin comprimir, código de programa, texto, etc.) tienden a ser muy repetitivos y muy diferentes a un archivo aleatorio de longitud similar. Básicamente, esos archivos "naturales" forman solo un pequeño subconjunto de todos los archivos de su longitud, y el software de compresión inteligente puede identificar dichos archivos repetitivos y acortarlos, mientras aumenta (ligeramente) la longitud de otros archivos de entrada de aspecto más aleatorio.

También es posible hacer esto de manera que se garantice que nunca aumentará la longitud de ningún archivo en más de un pequeño número fijo de bits, incluso en el peor de los casos. De hecho, es posible tomar cualquier esquema de compresión sin pérdidas$f$y convertirlo en un esquema$f'$que es casi tan eficiente y solo aumenta la longitud de cualquier archivo de entrada en un bit como máximo: simplemente defina

$$f'(x) = \begin{cases} (0, f(x)) & \text{if } \operatorname{len}(f(x)) < \operatorname{len}(x) \\ (1, x) & \text{otherwise,} \end{cases}$$ dónde$(b, x)$denota anteponer el bit$b$al archivo$x$.

Como otros han señalado, esto no puede funcionar por razones generales.

Sin embargo, puede estar más interesado en comprender dónde se descompone su análisis para este esquema específico.

Considere un cubo de$n^3$pedacitos En cada fila hay$2^n$diferentes combinaciones, así que si puedes almacenar$k$valores para cada entrada en uno de los tres lados, en el mejor de los casos puede reducir el número de posibilidades a$2^n/k$.

En tu ejemplo para$n=1000$y al usar números primos, debe y puede almacenar no valores reales hasta 7919, sino la suma de los primeros 1000 números primos, lo que requiere 7 dígitos decimales. En cualquier caso, habría 10000000 valores diferentes para codificar$2^{1000}\approx 10^{300}$diferentes combinaciones, por lo que en el mejor de los casos, un valor en el lado corresponde a$10^{293}$diferentes combinaciones de bits en esa fila. Incluso proyectar en las diferentes direcciones no hará una diferencia significativa.

Si desea que esto funcione, necesita muchos más dígitos para almacenar sus sumas, o ir a una dimensión muy alta en lugar de 3. En ambos casos, los datos adicionales requeridos para transmitir serán iguales a nuestra cantidad original de datos.

Extrapolando lo que dijo, el uso de números primos dañará la compresión de datos, no la ayudará.

Supongamos que tenemos una secuencia de 8 bits: ($b_0, b_1, b_2, b_3, b_4, b_5, b_6, b_7$).

Podríamos hacer un producto de números primos para codificar esa secuencia de bits:$x = 2^{b_0} × 3^{b_1} × 5^{b_2} × 7^{b_3} × 11^{b_4} × 13^{b_5} × 17^{b_6} × 19^{b_7}$.

Pero ahora el rango de valores posibles de$x$es$[1, 9699690]$, que necesitaría 24 bits para representar en notación estándar. Esto es mucho peor que nuestros 8 bits originales.

Sin embargo, los productos de números primos se pueden usar para pruebas matemáticas teóricas: https://en.wikipedia.org/wiki/G%C3%B6del_numbering

Es un comentario, simplemente no encaja.

Como uno de esos tipos con conexiones lentas, agradezco los esfuerzos.

Youtube es bueno para mí exactamente porque tiene videos de 144p, y si algo es interesante o lo necesito, puedo elegir qué xxxp configurar.

Pero tiene sus problemas de conmutación y almacenamiento en búfer que probablemente no tendría si esa variedad de resoluciones se implementara o lograra de manera diferente.

En los viejos tiempos de los módems, se veía con más frecuencia, una imagen que comienza con unos pocos píxeles enormes y luego se detalla a medida que se descargan más datos. No estoy seguro de qué compresión era, pero parece un jpeg con esteroides. Esos fragmentos de datos podrían definirse como n-streams para video o múltiples imágenes, y podría brindar un control más preciso del lado del usuario, pero estableciendo un límite en la cantidad de canales para solicitar, o ajustarlo automáticamente.

Entonces, tal vez mire no en la dirección de cuánto comprimir, sino en cómo controlar la calidad. Todos los formatos de compresión de tasa de bits fija y tasa de bits variable hacen que varíe la calidad o intente mantener la calidad. Pero producen un blob de datos, y administrar diferentes resoluciones puede ser un desafío en el lado del servidor, por lo que el usuario no tiene tantas opciones (me alegro de que haya algunos lugares donde uno tiene), retrasos en la calidad de cambio, etc., etc.

Entonces, tal vez, como sugerencia, aborde el problema desde una perspectiva diferente: un control de calidad más flexible en el lado del usuario y del servidor. Transición más fluida de una calidad a otra y similares.

Las personas con conexiones más lentas ya hacen compromisos y seguro que aprecian los lugares que ofrecen opciones adecuadas. De la misma manera que no hay alternativa para YouTube para mí porque la menor calidad que he visto fue 360p y es de la mejor calidad para mí (con algunas dificultades, si el clima es bueno, por así decirlo) si ellos (alternativas) tienen tales opciones en absoluto . A veces no me importaría 100p o no necesitaría video en absoluto hasta que lo haga, y cuando lo haga, me gustaría no descartar el búfer de 1 minuto ya existente, sino agregarlo para mejorar la calidad.

Por lo tanto, las mejores herramientas, opciones y enfoques para luchar contra todos esos compromisos pueden ser más apreciados que un algoritmo sorprendente que funciona un 10 % mejor que todos los algoritmos existentes en cualquier dato. Al variar la calidad, obtengo una reducción del 90% de los datos la mayor parte del tiempo: cuando los detalles comienzan a ser importantes, entonces sí, es hora de armas pesadas como esperar un búfer y otras opciones disponibles.

En general, intercambiar recursos de usuario por menos transferencia de datos no es imposible, y no es necesariamente un problema puramente matemático, como 5 oraciones que describen un manzano o una imagen, y el lado del usuario ai genera uno o encuentra visualmente similar en un diccionario, etc. Pero es un problema un poco más amplio.