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

Es un comentario, simplemente no encaja

Como uno de esos chicos con conexiones lentas, aprecio 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 establecer.

Pero tiene sus problemas al cambiar y almacenar en búfer que probablemente no tendría si esa variedad de resoluciones se implementara/lograra de manera diferente.

En los buenos viejos tiempos de los módems, era más común ver una imagen que comienza con unos pocos píxeles enormes y luego se detalla a medida que se descarga 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-flujos para video o múltiples imágenes, y podría ofrecer un control más fino en el lado del usuario, pero estableciendo un límite en cuántos canales solicitar, o ajustándolo automáticamente.

Así que tal vez echar un vistazo no en la dirección de cuánto comprimir, sino cómo controlar la calidad. Todos los formatos de compresión de tasa de bits fija y variable hacen eso variando la calidad o intentando mantener la calidad. Pero producen un bloque de datos, y gestionar diferentes resoluciones puede ser desafiante en el lado del servidor, por lo que el usuario no tiene tantas opciones (me alegro de que haya lugares donde se tengan), retrasos al cambiar la calidad, etc, etc.

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

Las personas con conexiones más lentas ya hacen compromisos y seguramente aprecian lugares que ofrecen opciones adecuadas. De la misma manera que no hay alternativa para mí a Youtube porque la calidad mínima que he visto fue 360p y es de alta calidad para mí (con algunas dificultades, si el clima es adecuado, por así decirlo) si tienen tales opciones en absoluto. A veces no me importaría 100p o no necesito video en absoluto hasta que lo haga, y cuando lo hago, me gustaría que no descarte el búfer de 1 minuto existente sino que lo agregue para mejorar la calidad.

Así que mejores herramientas y opciones y enfoques para combatir todos esos compromisos pueden ser más apreciados que un algoritmo increíble que hace un 10% mejor que todos los algoritmos existentes en cualquier dato. Variando 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 tomar medidas drásticas como esperar un búfer y otras opciones disponibles.

En general, intercambiar recursos del usuario por una transferencia de datos menor no es imposible, y no necesariamente es puramente un problema matemático - como 5 oraciones describiendo un árbol de manzanas o una imagen, y el ai del usuario genera uno o encuentra visualmente similar en un diccionario, etc. Pero es un problema un poco más vasto.