Compresión de datos: codificación aritmética poco clara

Question

¿Puede alguien explicar la codificación aritmética de la compresión de datos con los detalles de implementación? He navegado a través de Internet y encontré la publicación de mark nelson, pero la técnica de implementación no me resulta clara después de intentar durante muchas horas. La explicación de

Mark Nelson en la codificación aritmética se puede situar en

http://marknelson.us/1991/02/01/arithmetic-coding-statistical-modeling-data-compression/

Answer 1

La idea principal con la compresión aritmética es su capacidad de codificar probabilidad utilizando la cantidad exacta de longitud de datos requerida.

Esta cantidad de datos es conocido, probado por Shannon, y puede calcularse simplemente usando la siguiente fórmula: -log2 (p)

Por ejemplo, si p = 50%, entonces se necesita 1 bit. Y si p = 25%, necesita 2 bits.

Eso es lo suficientemente simple para probabilidades que son potencia de 2 (y en este caso especial, la codificación de huffman podría ser suficiente). Pero, ¿y si la probabilidad es del 63%? Entonces necesitas -log2 (0.63) = 0.67 bits. Suena complicado ...

Esta propiedad es especialmente importante si su probabilidad es alta. Si puede predecir algo con un 95% de precisión, solo necesita 0.074 bits para representar una buena suposición. Lo que significa que vas a comprimir mucho.

Ahora, ¿cómo hacer eso?

Bueno, es más simple de lo que parece. Usted dividirá su rango dependiendo de las probabilidades. Por ejemplo, si tiene un rango de 100, 2 eventos posibles y una probabilidad del 95% para el primero, los primeros 95 valores indicarán "Evento 1" y los últimos 5 valores restantes indicarán "Evento 2". .

Bien, pero en las computadoras, estamos acostumbrados a usar poderes de 2. Por ejemplo, con 16 bits, tiene un rango de 65536 valores posibles. Haga lo mismo: tome el primer 95% del rango (que es 62259) para decir "Evento 1", y el resto para decir "Evento 2". Obviamente tiene un problema de "redondeo" (precisión), pero siempre que tenga valores suficientes para distribuir, no importa demasiado. Además, no estás obligado a 2 eventos, podrías tener una gran cantidad de eventos. Todo lo que importa es que los valores se asignan según las probabilidades de cada evento.

Bien, pero ahora tengo 62259 valores posibles para decir "Evento 1" y 3277 para decir "Evento 2". Cuál debería elegir ? Bueno, cualquiera de ellos servirá. Ya sea 1, 30, 5500 o 62256, todavía significa "Evento 1".

De hecho, decidir qué valor seleccionar no dependerá de la conjetura actual, sino de las siguientes.

Supongamos que estoy teniendo "Evento 1". Así que ahora tengo que elegir cualquier valor entre 0 y 62256. En la próxima estimación, tengo la misma distribución (95% Evento 1, 5% Evento 2). Simplemente asignaré el mapa de distribución con estas probabilidades. Excepto que esta vez, se distribuye en 62256 valores. Y continuamos así, reduciendo el rango de valores con cada conjetura.

De hecho, estamos definiendo "rangos", que se estrechan con cada conjetura. En algún momento, sin embargo, hay un problema de precisión, porque quedan muy pocos valores.

La idea es simplemente "inflar" el rango nuevamente. Por ejemplo, cada vez que el rango está por debajo de 32768 (2^15), se obtiene la salida del bit más alto y se multiplica el resto por 2 (cambiando efectivamente los valores por un bit a la izquierda). Al hacer esto de manera continua, está produciendo bits uno por uno, ya que están siendo resueltos por la serie de suposiciones.

Ahora la relación con la compresión se vuelve obvia: cuando el rango se reduce rápidamente (por ejemplo, 5%), se generan muchos bits para volver al rango por encima del límite. Por otro lado, cuando la probabilidad es muy alta, el rango se estrecha muy lentamente. Incluso puede tener muchas suposiciones antes de enviar sus primeros bits. Así es como es posible comprimir un evento a "una fracción de un bit".

He utilizado intencionalmente los términos "probabilidad", "adivinar", "eventos" para mantener este artículo genérico. Pero para la compresión de datos, solo tiene que reemplazarlos con la forma en que desea modelar sus datos. Por ejemplo, el próximo evento puede ser el siguiente byte; en este caso, tienes 256 de ellos.

Answer 2

Ante todo gracias por introducirme en el concepto de la compresión aritmética!

I puede ver que este método tiene los siguientes pasos:

1. Creación de mapeo: Calcular la fracción de ocurrencia de cada carta que da un tamaño de rango para cada alfabeto. A continuación, ordenarlos y asignar rangos reales de 0 a 1
2. Dado un mensaje de calcular el rango (en mi humilde opinión bastante sencillo)
3. encontrar el código óptimo

La tercera parte es un poco complicado. Usa el siguiente algoritmo.

Sea b la representación óptima. Inicialízalo para vaciar la cadena (''). Deje x ser el valor mínimo e y el valor máximo.

1. x dobles y y: x = 2 * x, y = 2 * y
2. Si ambos son mayores que 1 append 1 a b. Vaya al paso 1.
3. Si ambos son menores que 1, añada 0 a b. Vaya al paso 1. Si
4. < x 1, pero y> 1, tiene que poner 1 a B y deje de

b contiene esencialmente la parte fraccionaria del número que se está transmitiendo. P.ej. Si b = 011, entonces la fracción corresponde a 0.011 en binario.

¿Qué parte de la implementación no comprende?

Answer 3

Quizás esta secuencia de comandos podría ser útil para construir un mejor modelo mental del codificador aritmético: gen_map.py. Originalmente fue creado para facilitar la depuración de la biblioteca de codificadores aritméticos y simplificar la generación de pruebas unitarias para él. Sin embargo, crea agradables visualizaciones ASCII que también podrían ser útiles para comprender la codificación aritmética.

Un pequeño ejemplo. Imagine que tenemos un alfabeto de 3 símbolos: 0, 1 y 2 con probabilidades 1/10, 2/10 y 7/10 correspondientemente. Y queremos codificar la secuencia [1, 2].Escritura dará la siguiente salida (ignorar -b N opción por ahora):

$ ./gen_map.py -b 6 -m "1,2,7" -e "1,2" 
000000111111|1111|111222222222222222222222222222222222222222222222 
------011222|2222|222000011111111122222222222222222222222222222222 
---------011|2222|222-------------00011111122222222222222222222222 
------------|----|-------------------------00111122222222222222222 
------------|----|-------------------------------01111222222222222 
------------|----|------------------------------------011222222222 
================================================================== 
000000000000|0000|000000000000000011111111111111111111111111111111 
000000000000|0000|111111111111111100000000000000001111111111111111 
000000001111|1111|000000001111111100000000111111110000000011111111 
000011110000|1111|000011110000111100001111000011110000111100001111 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
001100110011|0011|001100110011001100110011001100110011001100110011 
010101010101|0101|010101010101010101010101010101010101010101010101 

Primeros 6 líneas (antes de ==== línea) representan una gama de 0.0 a 1.0 que se subdivide de forma recursiva en intervalos proporcionales a las probabilidades de símbolos. Anotada primera línea:

[1/10][  2/10 ][     7/10      ] 
000000111111|1111|111222222222222222222222222222222222222222222222 

Luego subdividir cada intervalo de nuevo:

[ 0.1][  0.2  ][     0.7      ] 
000000111111|1111|111222222222222222222222222222222222222222222222 
     [ 0.7 ][.1][ 0.2 ][   0.7     ] 
------011222|2222|222000011111111122222222222222222222222222222222 
            [.1][ .2][ 0.7    ] 
---------011|2222|222-------------00011111122222222222222222222222 

Tenga en cuenta, que algunos intervalos que no se subdividen. Eso sucede cuando no hay suficiente espacio para representar cada subintervalo dentro de la precisión dada (que se especifica mediante la opción -b).

Cada línea corresponde a un símbolo de la entrada (en nuestro caso - secuencia [1, 2]). Al seguir los subintervalos para cada símbolo de entrada obtendremos un intervalo final que queremos codificar con una cantidad mínima de bits. En nuestro caso se trata de una primera 2 subintervalo en una segunda línea:

  [ This one ] 
------011222|2222|222000011111111122222222222222222222222222222222 

Después de 7 líneas (después de ====) representan el mismo intervalo de 0,0 a 1,0, pero subdivide según notación binaria. Cada línea es un poco de salida y al elegir entre 0 y 1, elige medio-subintervalo izquierdo o derecho. Por ejemplo los bits 01 corresponde a subintervalo [0.25, 05) en una segunda línea:

    [ This one ] 
000000000000|0000|111111111111111100000000000000001111111111111111 

La idea de codificador aritmético es a bits de salida (0 o 1) hasta que el intervalo correspondiente será completamente en el interior (o igual a) el intervalo determinado por la secuencia de entrada. En nuestro caso es 0011. La línea ~~~~ muestra dónde tenemos suficientes bits para identificar inequívocamente el intervalo que queremos.

Las líneas verticales formadas por el símbolo | muestran el rango de secuencias de bits (filas) que se podrían usar para codificar la secuencia de entrada.