¿Cuál es la forma más eficiente de almacenar un rango numérico?

Esta pregunta es acerca de cuántos bits se requieren para almacenar un rango. O dicho de otra manera, para un número dado de bits, ¿cuál es el rango máximo que se puede almacenar y cómo?

Imagina que queremos almacenar un subrango dentro del rango 0-255.

Entonces, por ejemplo, 45-74.

Podemos almacenar el ejemplo anterior como dos bytes sin firmar, pero me parece que debe haber cierta redundancia de información allí. Sabemos que el segundo valor es mayor que el primero, por lo que en el caso de que el primer valor sea grande, se requieren menos bits para el segundo valor, y en el caso de que el segundo valor sea grande, se requieren menos bits para el primero .

Sospecho que cualquier técnica de compresión arrojaría un resultado marginal, por lo que podría ser una mejor pregunta: "¿cuál es el rango máximo que podría almacenarse en un byte?". Esto debería ser mayor de lo que se puede lograr almacenando los dos números por separado.

¿Hay algún algoritmo estándar para hacer este tipo de cosas?

Solo cuenta el número de rangos posibles. Hay 256 rangos con límite inferior 0 (0-0, 0-1, ... 0-254, 0-255), 255 rangos con límite inferior 1, ... y finalmente 1 rango con límite inferior 255 (255- 255). Entonces el número total es (256 + 255 + ... + 1) = 257 * 128 = 32,896. Como esto es ligeramente superior a 2 ¹⁵ = 32,768, aún necesitará al menos 16 bits (2 bytes) para almacenar esta información.

En general, para números desde 0 hasta n-1, el número de rangos posibles es n * (n + 1) / 2. Esto es menor que 256 si n es 22 o menos: n = 22 da 22 * ​​23/2 = 253 posibilidades. Entonces, un byte es suficiente para subrangos de 0-21 .

Otra forma de ver el problema es la siguiente: almacenar un par de enteros en el rango de 0 a n-1 es casi lo mismo que almacenar un subrango de 0- (n-1) más un solo bit que determina si el primer número es más bajo o más alto que el segundo. (La diferencia proviene del caso en que ambos enteros son iguales, pero esta posibilidad se vuelve cada vez más pequeña a medida que n crece). Es por eso que solo puede ahorrar un solo bit con esta técnica, y probablemente la razón principal por la que rara vez se usa.

Para un número tan pequeño de bits, no es factible guardar muchos bits como Glorfindel ha señalado . Sin embargo, si el dominio que está utilizando tiene algunos bits más, puede lograr ahorros significativos para el caso promedio codificando rangos con el valor inicial y un delta.

Supongamos que el dominio son los enteros, entonces 32 bits. Con el enfoque ingenuo, necesita 64 bits (inicio, fin) para almacenar un rango.

Si cambiamos a una codificación de (inicio, delta), podemos construir el final del rango a partir de eso. Sabemos que en el peor de los casos, el inicio es 0 y el delta tiene 32 bits.

2 ^ 5 es 32, por lo que codificamos la longitud del delta en cinco bits (sin longitud cero, siempre sumamos 1), y la codificación se convierte en (inicio, longitud, delta). En el peor de los casos, esto cuesta 32 * 2 + 5 bits, por lo que 69 bits. Entonces, en el peor de los casos, si todos los rangos son largos, esto es peor que la codificación ingenua.

En el mejor de los casos, cuesta 32 + 5 + 1 = 38 bits.

Esto significa que si tiene que codificar muchos rangos, y esos rangos solo cubren una pequeña parte de su dominio, termina usando menos espacio en promedio usando esta codificación. No importa cómo se distribuyen los inicios, ya que el inicio siempre tomará 32 bits, pero sí importa cómo se distribuyen las longitudes de los rangos. Si las longitudes más pequeñas que tiene, mejor es la compresión, más rangos tiene que cubren la longitud completa del dominio, peor será esta codificación.

Sin embargo, si tiene muchos rangos agrupados en torno a puntos de inicio similares (por ejemplo, porque obtiene valores de un sensor), puede lograr ahorros aún mayores. Puede aplicar la misma técnica al valor inicial y usar un sesgo para compensar el valor inicial.

Digamos que tienes 10000 rangos. Los rangos se agrupan alrededor de un cierto valor. Codifica el sesgo con 32 bits.

Usando el enfoque ingenuo, necesitaría 32 * 2 * 10 000 = 640 000 bits para almacenar todos esos rangos.

Codificar el sesgo requiere 32 bits, y codificar cada rango requiere, en el mejor de los casos, 5 + 1 + 5 + 1 = 12 bits, para un total de 120 000 + 32 = 120 032 bits. En el peor de los casos, necesita 5 + 32 + 5 + 32 bits, por lo tanto 74 bits, para un total de 740 032 bits.

Esto significa que, para 10 000 valores en un dominio que requiere 32 bits para codificar, obtenemos

• 120 032 bits con la codificación inteligente delta en el mejor de los casos
• 640 000 bits con el comienzo ingenuo, la codificación final, siempre (no hay mejor ni peor caso)
• 740 032 bits con la codificación inteligente delta en el peor de los casos

Si toma la codificación ingenua como línea de base, eso significa ahorros de hasta 81.25% o hasta 15.625% más de costo.

Dependiendo de cómo se distribuyan sus valores, esos ahorros son significativos. ¡Conozca su dominio comercial! Sepa lo que quiere codificar.

Como extensión, también puede cambiar el sesgo. Si analiza los datos e identifica grupos de valores, puede ordenar los datos en cubos y codificar cada uno de esos cubos por separado, con su propio sesgo. Esto significa que puede aplicar esta técnica no solo a los rangos que se agrupan alrededor de un solo valor inicial, sino también a los rangos que se agrupan alrededor de varios valores.

Si sus puntos de inicio se distribuyen por igual, esta codificación realmente no funciona tan bien.

Esta codificación es obviamente extremadamente mala para indexar. No puede simplemente leer el valor x-th. Solo se puede leer secuencialmente. Lo cual es apropiado en algunas situaciones, por ejemplo, transmisión a través de la red o almacenamiento masivo (por ejemplo, en cinta o HDD).

Evaluar los datos, agruparlos y elegir el sesgo correcto puede ser un trabajo sustancial y puede requerir algunos ajustes para obtener resultados óptimos.

Este tipo de problema es el tema del artículo seminal de Claude Shannon, A Mathematical Theory of Communication , que introdujo la palabra "bit" y más o menos inventó la compresión de datos.

La idea general es que el número de bits utilizados para codificar un rango es inversamente proporcional a la probabilidad de que ocurra ese rango. Por ejemplo, supongamos que el rango 45-74 aparece aproximadamente 1/4 del tiempo. Se puede decir que la secuencia 00 corresponde a 45-74. Para codificar el rango 45-74, debe emitir "00" y detenerse allí.

Supongamos también que los rangos 99-100 y 140-155 aparecen cada uno aproximadamente 1/8 de las veces. Puede codificar cada uno de ellos con una secuencia de 3 bits. Cualquier 3 bits funcionará siempre que no comiencen con "00", que ya se ha reservado para el rango 45-74.

00: 45-74
010: 99-100
101: 140-155

Puede continuar de esta manera hasta que cada rango posible tenga una codificación. El rango menos probable puede necesitar más de 100 bits. Pero está bien porque rara vez aparece.

No son algoritmos para encontrar el óptimo de codificación. No intentaré explicarlos aquí, pero puede encontrar más visitando el enlace de arriba o buscando "Teoría de la información", "Codificación de Shannon-fano" o "Codificación de Huffman".

Como otros han señalado, probablemente sea mejor almacenar el número inicial y la diferencia entre el número inicial y el final. Debería usar una codificación para el inicio y otra para la diferencia, ya que tienen diferentes distribuciones de probabilidad (y supongo que la última es más redundante). Como sugirió polygnome, el mejor algoritmo depende de su dominio.

Para ampliar la respuesta de @Glorfindel:

Como n → ∞, (n - 1) → n. Por lo tanto, Ω (rangos) → n² / 2 y log (Ω (rangos)) → (2n - 1). Dado que la codificación ingenua toma 2n bits, la compresión máxima asintótica solo ahorra 1 bit.

Hay una respuesta similar, pero para lograr una compresión óptima, necesita:

1. Un método de codificación de entropía óptimo (lea sobre codificación aritmética y el ANS esencialmente equivalente (misma relación de compresión, un poco más rápido pero también más difícil de comprender) )
2. La mayor cantidad de información posible sobre la distribución de los datos. De manera crucial, esto no solo implica "adivinar" con qué frecuencia puede aparecer un número, sino que a menudo puede descartar ciertas posibilidades con seguridad. Por ejemplo, puede descartar intervalos de tamaño negativo y posiblemente de tamaño 0, dependiendo de cómo defina un intervalo válido. Si tiene varios intervalos para codificar a la vez, puede ordenarlos, por ejemplo, en orden de disminución del ancho, o aumentar el valor inicial / final, y descartar una gran cantidad de valores (por ejemplo, si garantiza un pedido disminuyendo el ancho, el intervalo anterior tenía un ancho de 100, y el valor inicial para el siguiente es 47, solo necesita considerar las posibilidades de hasta 147 para los valores finales).

Es importante destacar que el número 2 significa que desea codificar las cosas de tal manera que los valores más informativos (por bit codificado) sean lo primero. Por ejemplo, aunque sugerí codificar una lista ordenada "tal cual", generalmente sería más inteligente codificarla como un "árbol binario", es decir, si están ordenados por ancho y tiene lenelementos, comience por codificar el elemento len/2. Digamos que tenía ancho w. Ahora conoce todos los elementos antes de que tenga ancho en algún lugar en [0, w], y todos los elementos después de que tenga ancho en algún lugar en [w, valor máximo que acepta]. Repita de forma recursiva (subdividiendo cada mitad de la lista nuevamente por la mitad, etc.) hasta que haya cubierto los lenelementos (a menos que esté arreglado, querrá codificarlenprimero para que no tenga que preocuparse por terminar con los tokens). Si "max val you accept" está realmente abierto, puede ser inteligente codificar primero el valor más alto que realmente aparece en sus datos, es decir, el último elemento, y luego realizar la partición binaria. De nuevo, lo que sea más informativo por bit primero.

Además, si está codificando el ancho del intervalo primero, y sabe el valor máximo posible con el que está tratando, obviamente puede descartar todos los valores iniciales que harían que se desborde ... se le ocurre la idea. Transforme y ordene sus datos de tal manera que pueda inferir tanto como sea posible sobre el resto de los datos mientras los decodifica, y un algoritmo de codificación de entropía óptimo se asegurará de que no esté desperdiciando bits que codifican información que "ya conoce" .