Reduciendo el tiempo de descarga utilizando números primos

Question

Recientemente ha surgido un problema en la programación del cual podría beneficiarme enormemente de la experiencia de matemáticos adecuados. El problema del mundo real es que las aplicaciones a menudo necesitan descargar grandes cantidades de datos de un servidor, como videos e imágenes, y los usuarios podrían enfrentarse al problema de no tener una gran conectividad (por ejemplo, 3G) o podrían estar en un plan de datos caro.

En lugar de descargar un archivo completo, he estado tratando de demostrar que es posible en su lugar descargar una especie de 'reflejo' del mismo y luego, utilizando la potente capacidad de cálculo del teléfono inteligente, reconstruir con precisión el archivo localmente utilizando la probabilidad.

La forma en que funciona es la siguiente:

1. Un archivo se descompone en sus bits (1,0,0,1, etc.) y se dispone en un patrón predeterminado en forma de cubo. Como ir de adelante hacia atrás, de izquierda a derecha, y luego hacia abajo en una fila, hasta completar. El patrón no importa, siempre y cuando se pueda revertir después.
2. Para reducir el tamaño del archivo, en lugar de solicitar todo el cubo de datos (equivalente a descargar el archivo completo), solo descargamos 3 x 2D lados en su lugar. A estos lados los llamo el reflejo por falta de un mejor término. Tienen los contenidos del cubo asignados en ellos.
3. Luego se utiliza el reflejo para reconstruir el cubo 3D de datos usando la probabilidad, algo así como pedirle a una computadora que resuelva un enorme Sudoku tridimensional. Crear el reflejo y reconstruir los datos a partir de él genera una carga computacional pesada, y por más que a las computadoras les encante hacer matemáticas, me gustaría aligerar un poco su carga.

La forma en que lo imagino es como un cubo de Rubik transparente de 10x10. En tres de los lados, la luz brilla a través de cada fila. Cada celda por la que pasa tiene un valor predeterminado y está activada o desactivada (ya sea binario 1 o 0). Si está activada, magnifica la luz por su valor. Si está desactivada, no hace nada. Todo lo que vemos es la cantidad final de luz que sale de cada fila, después de atravesar el cubo desde el otro lado. Usando los tres lados, la computadora debe determinar qué valores (ya sea 1 o 0) están dentro del cubo.

En este momento estoy utilizando números primos normales como los valores de las celdas para reducir el tiempo de cálculo, pero me gustaría saber si hay otro tipo de primo (o un tipo de número completamente diferente) que podría ser más efectivo. Estoy buscando una serie de valores que tenga la menor combinación posible de componentes dentro de esa serie.

Aquí tienes un diagrama aproximado:

Puede ser útil imaginar que la luz brilla en las flechas verdes y sale con algún valor en las flechas rojas. Esto sucede para cada fila, en cada una de las tres direcciones. Nos quedan solo tres lados 2D de números, que se utilizan para reconstruir lo que hay dentro del cubo.

Si ves dónde sale el 14 en la izquierda, puede tener dos combinaciones posibles (3 + 11 y 2 + 5 + 7). Si por motivos de discusión asumiéramos que son 3 y 11 (coloreados de verde), entonces podríamos decir que en la coordenada donde existen el 3 y el 11, hay celdas activas (magnificando la luz por su valor). En términos de datos, diríamos que está activada (binario 1).

En la práctica, rara vez podemos decir con certeza (para 2 y 3 sí podríamos) cuál es el valor interno basado en su reflejo en la superficie, por lo que se asigna una probabilidad a esa coordenada o celda. Algunos números nunca se reflejarán en la superficie, como 1, 4 o 6, ya que no pueden componerse solo de primos.

Lo mismo ocurre en la dirección vertical, donde la salida es 30, lo cual tiene múltiples posibilidades de las cuales dos corresponden a la posibilidad mostrada en la dirección horizontal con una salida de 14, coloreadas de azul y rosa (ya que encuentran el 23, igual que el 3 en la dirección horizontal).

Esta probabilidad también se agrega a esa coordenada y repetimos en la dirección de adelante hacia atrás, haciendo lo mismo una última vez. Después de hacer esto para cada celda en todo el cubo, tenemos un conjunto de tres probabilidades de que una celda esté activada o desactivada. Eso se usa como punto de partida para ver si podemos completar el cubo. Si no se 'desbloquea', intentamos una combinación diferente de probabilidades y así sucesivamente hasta resolver el Sudoku 3D.

El paso final del método es una vez que se resuelve el cubo, la información binaria se extrae y se dispone en el patrón inverso a cómo se colocó en el servidor. Esto luego se puede dividir (por ejemplo, para múltiples imágenes) o utilizarse para crear un video o algo similar. Teóricamente podrías tos descargar algo como Avatar en 3D (280GB) en alrededor de 3 minutos con una buena conexión wifi. Resolverlo (sin mencionar construir la salida de píxeles) llevaría un tiempo, y aquí es donde tengo curiosidad sobre el uso de un número alternativo a los números primos.

Podrías haber adivinado que mi habilidad matemática se desploma bruscamente más allá de cosas rutinarias de programación. Hay tres áreas de preocupación / desventajas de este método:

1. es malo en niveles bajos de transferencia de datos. Un cubo de 10 x 10 x 10 por ejemplo tiene un 'área superficial' mayor que el volumen. Eso se debe a que aunque cada celda puede contener un bit (ya sea 1 o 0), cada celda superficial necesita ser un mínimo de 8 bits (un carácter es un byte, o 8 bits). Ni siquiera podemos tener 'nada', ya que necesitamos que el nulo funcione como un tipo de marcador de posición para mantener la estructura intacta. Esto también explica por qué en el diagrama anterior, un cubo de 1000x1000x1000 celdas tiene sus áreas superficiales multiplicadas por 4 caracteres (el milésimo primo es 7919 - 4 caracteres) y el cubo de 10'000 celdas tiene sus áreas superficiales multiplicadas por 6 caracteres (el 10'000º primo es 104729, seis caracteres). El objetivo es mantener la longitud total de caracteres en el lado 2D a un mínimo. Podría funcionar usar letras, ya que podríamos ir de a-Z con 52 símbolos, antes de pagar el doble por el siguiente carácter (equivalente a "10"). Hay 256 caracteres ASCII únicos, por lo que ahí está el límite superior.
2. los factoriales siguen siendo demasiado altos usando números primos. ¿Existe una serie de números que sean cortos en longitud de caracteres (para evitar el problema anterior) y tengan muy pocos posibles parientes? Estoy inclinado hacia algún subconjunto de primos, pero carezco del conocimiento matemático para saber cuál - ¿algún tipo de Fibonacci invertido? Cuantas menos combinaciones posibles, más rápido resolverá la computadora el cubo.
3. No he probado aún si es posible usar un tercer, cuarto u otro lado para aumentar la capacidad del cubo o la precisión del reflejo. Usar, por ejemplo, un octaedro (amarillo abajo) en lugar de un cubo podría ser mejor, solo duele un poco la cabeza pensar en cómo podría funcionar. Supongo que tendería hacia una esfera, pero eso está más allá de mi capacidad.

EDICIÓN:

Gracias por tu útil aportación. Muchas respuestas han hecho referencia al principio de las cajas del palomar y al problema de tener demasiadas combinaciones posibles. También debo corregir que un cubo de 1000 x requeriría 7 dígitos, no 4 como mencioné anteriormente, ya que la suma de los primeros 1000 primos es 3682913. También debo enfatizar que la idea no es comprimir en el sentido común de la palabra, como sacar píxeles de una imagen, sino más bien enviar planos sobre cómo construir algo, y depender únicamente de la computación y el conocimiento en el extremo receptor para completar los vacíos. Hay más de una respuesta correcta, y marcaré como correcta la que tenga más votos. Muchas gracias por las explicaciones detalladas y pacientes.

Answer 1

La compresión universal sin pérdida es imposible, esto no puede funcionar. El conjunto de cadenas binarias de longitud $n$ no es inyectivo en el 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$

Dado que $2^{n} > |S_{n-1}|$, el principio del palomar implica que no hay función inyectiva del conjunto de todas las cadenas binarias de longitud $n$ a ningún $S_{k}$ para $k. Esto significa que un esquema de compresión sin pérdida perfecto como el descrito es una imposibilidad ya que constituiría tal función.

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

Si asumes que esto no es el caso, tienes alguna función $g:P \to X$ donde $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}$. Nuevamente, por el principio del palomar, si todas las $2^{n}$ cadenas de longitud $n$ tienen un programa cuya longitud es menor que $n$, de las cuales solo puede haber $2^{n}-1$, debe haber un programa que produzca dos cadenas diferentes, de lo contrario el conjunto más grande no estaría cubierto. Nuevamente esto es absurdo, asi que al menos una de estas cadenas tiene una complejidad de al menos su propia longitud.

Editar: En respuesta a preguntas sobre la compresión con pérdida, este esquema parece poco probable que sea ideal para la gran mayoría de casos. No tienes forma de controlar dónde y cómo induce errores. Esquemas de compresión como H.264 aprovechan la estructura visual inherente de una imagen para lograr una mejor fidelidad a tamaños más pequeños. El método propuesto elegiría indiscriminadamente una solución al sistema de ecuaciones que genera, lo que probablemente introduciría artefactos notables. Creo que también es posible para estos sistemas estar sobredeterminados, utilizando 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 solver SAT/SMT, cuyo tiempo de ejecución haría la descompresión muy costosa, si no inabordable, mientras que las técnicas basadas en DCT están bien estudiadas y optimizadas para el rendimiento, aunque no soy un experto en ninguno de estos temas en absoluto.

Answer 2

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

Tienes una idea interesante y por favor continúa investigándola, ¿sabías que la compresión de datos ya tiene una amplia base de investigación? Es posible que quieras investigar si tu idea, o algo similar, ya está disponible. Hay un artículo de Wikipedia sobre compresión como punto de entrada al tema.

Algunas observaciones son:

1. Los archivos de sonido, películas e imágenes en uso por la mayoría de las aplicaciones están altamente comprimidos, generalmente (pero no siempre) usando algoritmos imperfectos con una pérdida de datos asociada. Por lo tanto, formatos como zip, jpeg, mp3, mov e incluso png, no están 'listos para usar' al llegar, sino que a veces necesitan un procesamiento extenso antes de su uso. Los algoritmos han evolucionado mucho en los últimos 50+ años y en algunos casos son altamente 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 un pequeño número de palabras diferentes) y funciona menos bien o no funciona en absoluto cuando los datos son verdaderamente aleatorios.

3. En algunas aplicaciones, la pérdida de datos puede ser aceptable, por ejemplo en una imagen o en música donde el ojo u 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 ej. reducción del 90% en tamaño). Pero para muchos propósitos necesitas 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 texto. Los datos a menudo aún pueden comprimirse, explotando 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 por lo tanto menos susceptibles a una mayor compresión, por lo que intentar comprimir un archivo jpg o mp3 generalmente no ahorrará nada e incluso puede ocupar más espacio.

Answer 3

Comenzaré confesando que no leí toda la descripción de tu esquema de compresión en detalle. Realmente no necesito hacerlo, ya que lo que estás intentando lograr es un esquema de compresión de datos sin pérdida agnóstico de la entrada, y eso es imposible.

Teorema 1: No existe un esquema de compresión sin pérdida que mapee cada archivo de longitud $n$ bits a un archivo de longitud menor que $n$ bits.

La prueba sigue fácilmente del principio de las casillas y el hecho de que hay $2^n$ archivos distintos de $n$ bits pero solo $2^n-1$ archivos distintos de menos de $n$ bits. Esto implica que cualquier esquema de compresión que mapee archivos de $n$ bits a archivos de menos de $n$ bits debe mapear al menos dos archivos de entrada al mismo archivo de salida, y por lo tanto no puede ser sin pérdida.

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

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

Necesitamos un poco de notación adicional. Específicamente, dejemos que $\operatorname{len}(x)$ denote la longitud del archivo $x$, y dejemos que $\operatorname{len}(S) = \sum_{x \in S} \operatorname{len}(x)$ denote la longitud total sumada de todos los archivos en el conjunto $S$. Por lo tanto, la longitud promedio de los archivos en $S$ es $\frac{\operatorname{len}(S)}{|S|}$, donde $|S|$ es el número de archivos en $S$. Además, $\operatorname{len}(R \cup S) = \operatorname{len}(R) + \operatorname{len}(S)$ para cualquier dos conjuntos disjuntos de archivos $R$ y $S$.

Ahora dejemos que $f$ sea un esquema de compresión sin pérdida, es decir, una función que mapea archivos a archivos, dejemos que $A$ sea el conjunto de todos los archivos de longitud a lo sumo $n$ bits, y dejemos que $B = \{f(x) : x \in A\}$ sea el conjunto de archivos obtenidos aplicando $f$ a cada archivo en $A$. Dado que $f$ es sin pérdida, debe mapear cada archivo de entrada en $A$ a un archivo de salida distinto; por lo tanto, $|B| = |A|$, y por lo tanto también $|A \setminus B| = |B \setminus A|$.

Dado que $A$ es el conjunto de todos los archivos de a lo sumo $n$ bits de longitud, se sigue que $\operatorname{len}(x) ≤ n$ si y solo si $x \in A$. Por lo tanto, $$\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$, implicando que $A \setminus B = B \setminus A = \emptyset$).

Además, dado que $A \cap B$ es disjunto tanto de $A \setminus B$ como de $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 dado que $|A| = |B|$, como se mencionó anteriormente, tenemos $\frac{\operatorname{len}(A)}{|A|} ≤ \frac{\operatorname{len}(B)}{|B|}$ (donde, nuevamente, la desigualdad es estricta a menos que $A = B$).

---

Pd. Entonces, ¿cómo funcionan los esquemas de compresión sin pérdida del mundo real? Simplemente, 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 altamente repetitivos y bastante 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 esos archivos repetitivos y acortarlos, mientras (ligeramente) aumenta la longitud de otros archivos de entrada que parecen más aleatorios.

También es posible hacer esto de una manera que garantice 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érdida $f$ y convertirlo en un esquema $f'$ que sea casi tan eficiente y solo aumente la longitud de cualquier archivo de entrada en a lo sumo un bit: simplemente define $$f'(x) = \begin{cases} (0, f(x)) & \text{si } \operatorname{len}(f(x)) < \operatorname{len}(x) \\ (1, x) & \text{en otro caso,} \end{cases}$$ donde $(b, x)$ denota anteponer el bit $b$ al archivo $x$.

Answer 4

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

Sin embargo, es posible que estés más interesado en entender dónde falla su análisis para este esquema específico.

Considera un cubo de $n^3$ bits. En cada fila hay $2^n$ combinaciones diferentes, por lo que si puedes almacenar $k$ valores para cada entrada en uno de los tres lados, como máximo puedes reducir el número de posibilidades a $2^n/k$.

En tu ejemplo para $n=1000$ y usando números primos, necesitas ser capaz de almacenar no realmente valores hasta 7919, sino la suma de los primeros 1000 números primos, lo cual requiere 7 dígitos decimales. De cualquier manera, habría 10000000 valores diferentes para codificar $2^{1000}\approx 10^{300}$ combinaciones diferentes, así que en el mejor de los casos, un valor en el lado corresponde a $10^{293}$ combinaciones diferentes de bits en esa fila. Incluso proyectando en diferentes direcciones no hará una diferencia significativa.

Si quieres hacer que esto funcione, necesitas muchos más dígitos para almacenar tus sumas, o pasar a una dimensión mucho más alta que 3. En ambos casos, los datos extras necesarios para transmitir serán iguales o excederán la cantidad original de datos.

Answer 5

Extrapolando de lo que dijiste, usar números primos daña la compresión de datos, no la ayuda.

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]$, lo cual tomaría 24 bits para representar en notación estándar. Esto es mucho peor que nuestros originales 8 bits.

Los productos de números primos pueden ser usados para demostraciones matemáticas teóricas: https://en.wikipedia.org/wiki/G%C3%B6del_numbering