¿Cuál es la forma más eficiente en cuanto al espacio para almacenar una gran variedad de enteros, donde todos los enteros están entre 0-2, inclusive?

Answer 1

2 bits por entero desperdician una fracción de un bit. La matriz requiere 2n bits de espacio pero solo transmite aproximadamente 1,6n bits de información. Solo se utilizan tres de las cuatro “palabras clave” posibles, una eficiencia del 75% (o una eficiencia teórica de la información de aproximadamente el 79%).

Para obtener una mayor eficiencia, una forma es pasar a palabras de código más largas. En lugar de tratar nuestras palabras de entrada como “0”, “1” y “2”, podemos usar palabras de varios dígitos. Por ejemplo, tomamos dos dígitos a la vez que serían 9 posibilidades (¡peor aún, necesitaríamos 4 bits!) Si tomamos K dígitos a la vez, entonces tenemos [matemáticas] 3 ^ K [/ matemáticas] palabras, entonces queremos una potencia de 3 que esté cerca (pero por debajo) de una potencia de 2.

[matemáticas] 3 ^ 2 = 9 <16 [/ matemáticas]
[matemáticas] 3 ^ 3 = 27 <32 [/ matemáticas]
[matemáticas] 3 ^ 4 = 81 <128 [/ matemáticas]
[matemáticas] 3 ^ 5 = 243 <256 [/ matemáticas]

Entonces, con palabras de cinco dígitos podemos obtener casi un 95% de eficiencia. (Simplemente escriba las secuencias de 00000 a 22222 en orden, numerelas y use la representación binaria de esa numeración).

Para manejar palabras que no son múltiplos de cinco bits, podemos hacer que un valor especial indique un cambio a la codificación de 2 bits. Esto no hace ninguna diferencia en la eficiencia asintótica.

Sin embargo, todavía nos quedan algunas fracciones. Podemos aumentar ligeramente la eficiencia utilizando los 12 códigos restantes de ocho bits (excluyendo nuestro valor especial) para algunas palabras de seis dígitos. Sin embargo, eso dificulta el acceso aleatorio a la matriz, por lo que, dependiendo de su aplicación, eso podría ser indeseable.

Answer 2

primero, representarlo a nivel de bits de forma compacta. 0,1,2 no ocupa 2 bits completos. 3 sería una entrada no válida y, por lo tanto, se desperdicia espacio. Entonces, no necesitamos almacenarlo.
0: 00
1: 01
2: 1

Bajo este esquema, si encontramos un bit 0, también leemos el siguiente bit, para darnos un 0 o un 1, luego continuamos. si es un 1, entonces sabemos que tenemos un 2, y luego pasamos al siguiente dígito. Esto significa que carece de acceso aleatorio, pero en el espacio es muy eficiente.

Entonces, por ejemplo, 002211022102 se convierte en
0000110101001101001

un esquema de codificación ingenuo sería
000010100101001010010010

Como puede ver, esto le ahorra un poco cada vez que tiene un 2.
Si la distribución de los dígitos es desigual, puede definir que el dígito más común sea el único bit y luego definir los códigos 01 y 00 para que correspondan con los otros dos dígitos, pero esto solo ayuda si van a ser desiguales.
También podría intentar ejecutar un algoritmo de compresión sobre esta cadena, que puede o no proporcionarle ahorros adicionales, dependiendo de qué tan comprimibles sean los datos que está almacenando.

Answer 3

Puede almacenar solo un bit cuando el número es cero con el número 0 en él. Cuando el bit es 1, sabe que el siguiente bit le dirá si el número es 1 o 2.

Solo verificará el segundo bit como parte del número cuando el primer bit sea uno.

Básicamente :
0-0
10-1
11-2

Un ejemplo de secuencia será:
0 1 0 1 1

Esa secuencia representa:
0 1 2

Espero que esto ayude. Esto es algo así como un Huffman encontrando. Puede establecer el valor 0 para que sea el dígito más común en su distribución.

Answer 4

muchas respuestas han sugerido (correctamente) usar un código sin prefijo. esa estrategia es óptima (es decir, sin desperdicio) si y solo si a) asigna los códigos más cortos a los símbolos con mayor probabilidad yb) las probabilidades de sus símbolos son potencias de dos.
mucho depende de la distribución de sus símbolos: en ciertos casos, podría usar la codificación de longitud de ejecución: tome una secuencia de 0,1,2 y codifíquela reemplazando las ejecuciones (secuencias máximas del mismo símbolo) con el símbolo y el longitud de la carrera. por ejemplo, 1111110111111111002 sería <1,6>, <0,1>, <1,9>, <0,2>, <2.1>

Answer 5

Al representar los números como

0: 0

1:10

2: 11

Usted promedia 1,666 bits por valor almacenado. Esto es óptimo y refleja la cantidad real de información en la fuente.

Si los números no se distribuyeron de manera uniforme (es decir, hubo desproporcionadamente muchos 2), entonces use 0 para representar el valor más común. Esto sería esencialmente una codificación de Huffman.

Answer 6

Considere toda la matriz como un número base 3 y almacene el número.
Es el más eficiente en cuanto al espacio, pero acceder a un solo valor no será eficiente desde el punto de vista computacional.
Para una matriz con 100 celdas necesitará ceil (log2 (3 ^ 100)) = 159 bits.

Answer 7

Dado que el número de opciones posibles para una cadena de 3 símbolos (3 para 1 carácter, 9 para 2 caracteres, 27 para 3 caracteres) nunca se alineará para ser una potencia de 2, siempre habrá memoria desperdiciada. Sin embargo, si imagina que su cadena es un número en base 3 y convierte ese número en base 2, sería una codificación más eficiente. No tengo una prueba de que sea mínima, pero sospecharía que está cerca.

Answer 8

Claro, puede almacenarlos en el módulo 3. Eso requiere mucha división y módulo 3, pero puede valer la pena.

Por ejemplo, en un número entero de 32 bits, puede almacenar 16 de ellos usando 2 bits cada uno, pero usando el módulo 3, puede almacenar 20 de ellos, como 3 ^ 20 = 3,486,784,401 que cabe en 32 bits.

Además, dado que hay tan pocos valores, existe una posibilidad considerable de que se ejecuten los mismos valores repetidos, por lo que puede usar algo de codificación de longitud de ejecución.

Además, si hay un gran desequilibrio en las proporciones, como muchos de 2, puede usar la codificación Huffman, donde un bit ‘0’ significa ‘2’, entonces ’10’ significa ‘0’ y ’11’ significa ‘1’ .

Answer 9

Incorrecto: no hay espacio perdido. 0 = 00; 1 = 01; 2 = 10; 11 no se utiliza, pero todos los valores válidos son 2 bits …