Codificación aritmética
La codificación aritmética es una codificación de entropía utilizada en la compresión de datos sin pérdida. Proporciona una mejor compresión que la codificación de Huffman , excepto cuando todos los pesos de las hojas / nodos / raíces del árbol de Huffman son potencias de 2 , en cuyo caso los dos métodos son equivalentes.
A pesar de esta ventaja, apenas se utilizó porque su implementación era demasiado compleja; Los métodos de implementación se encontraron finalmente a medida que la compresión de diccionarios ( mucho mejor que Huffman o la codificación aritmética ) comenzó a ganar popularidad.
Sin embargo, tenga en cuenta su uso en la compresión de imágenes según los estándares JPEG 2000 y JBIG2 .
Principio
La codificación aritmética (como la codificación Huffman ) es un código de longitud variable, es decir que un símbolo de tamaño fijo (en bits ) será codificado por un número variable de bits, preferiblemente menor o igual a su tamaño original. Por tanto, no se modifica la densidad de los símbolos sino su codificación para reducir el espacio que ocupan.
Lo que diferencia la codificación aritmética de otras codificaciones de origen es que codifica el mensaje en partes (teóricamente puede codificar un mensaje completo de cualquier tamaño, pero en la práctica solo podemos codificar partes de unos quince símbolos en promedio) y representar cada una de estas partes por un número (punto flotante) donde Huffman codifica cada símbolo con un código específico. El problema resultante para la codificación de Huffman es que un carácter con una probabilidad de ocurrencia muy alta se codificará en al menos un bit. Por ejemplo, si buscamos codificar un carácter representado al 90%, el tamaño óptimo del código de carácter será de 0,15 bits, mientras que Huffman codificará este símbolo en al menos 1 bit, es decir, 6 veces más. Es este vacío el que la codificación aritmética llena gracias a un algoritmo cercano a la codificación de intervalo .
Propiedades
Compresión
La compresión requiere una tabla estadística (lo más cercana posible a las estadísticas observables en el archivo que contiene los símbolos a comprimir) que incluye:
- Todos los símbolos que se encuentran en el mensaje a comprimir.
- Las probabilidades de encontrar el símbolo en el mensaje.
- El intervalo dividido en intervalos proporcionales a la probabilidad de que el símbolo aparezca en el mensaje (por ejemplo: si hay un 50% de posibilidades de aparecer, su intervalo será de 0,5).
El objetivo ahora será aplicar una serie de operaciones a un intervalo dado (generalmente el intervalo que se elige) para modificar sus límites cada vez que se agrega un símbolo y limitar el número de posibilidades tanto como sea posible. salidas.
Estas son las operaciones que se deben realizar al agregar un símbolo :
- Se registra la diferencia entre el límite superior (BS) y el límite inferior (BI). Este valor se anotará BB.
- El BS toma el siguiente valor: BI + BB * (BS_du_symbole_s)
- El BI toma el siguiente valor: BI + BB * (BI_du_symbole_s)
Después de agregar el primer símbolo, el intervalo tendrá los mismos límites que el intervalo del símbolo agregado, luego cada adición convergerá en sus límites. Cuando se haya almacenado una cantidad suficiente de símbolos, el algoritmo devolverá un número flotante que se encuentre en este rango. Este número representa el archivo de entrada completo.
Observamos que una serie de símbolos que tienen una alta probabilidad de aparecer hará que el intervalo converja mucho más lentamente que si se tratara de una serie de símbolos que parecen pequeños. Por lo tanto, un número en un intervalo que ha convergido lentamente se codificará con menos dígitos significativos que un número en un intervalo extremadamente preciso, de ahí la ganancia.
También es necesario pensar en agregar un símbolo que se utilizará solo para indicar el final del archivo, de lo contrario, el algoritmo de descompresión corre el riesgo de ejecutarse indefinidamente, produciendo el archivo seguido de una secuencia pseudoaleatoria de bits.
Descompresión
Para descomprimir un archivo (representado por un número ), debe utilizar la misma tabla que se utilizó para la compresión y luego realizar los siguientes pasos hasta el final del archivo:
- Observe en el intervalo qué símbolo es el número, agregue al archivo descomprimido y guarde en memoria la probabilidad de así como su BI.
- toma valor .
Una vez que se alcanza el marcador final, el algoritmo se detiene y el archivo se considera descomprimido.
Ejemplo
Compresión
Se aplicará aquí el algoritmo de compresión aritmética sobre el texto “WIKI”. Por tanto, obtenemos la siguiente tabla:
| Letra | Probabilidad | Intervalo |
|---|---|---|
| W | 1/4 | [0; 0,25 [ |
| I | 2/4 | [0,25; 0,75 [ |
| K | 1/4 | [0,75; 1 [ |
Por convención, el algoritmo se inicializa con un límite inferior igual a 0 y un límite superior igual a 1. Solo queda aplicar la serie de operaciones vistas anteriormente a cada adición de un carácter.
| Carácter agregado | Límite inferior | Límite superior |
|---|---|---|
| 0 | 1 | |
| W | 0 | 0,25 |
| I | 0.0625 | 0,1875 |
| K | 0.15625 | 0,1875 |
| I | 0.1640625 | 0.1796875 |
Entonces, cualquier número en el rango será una versión comprimida de la cadena "WIKI". Incluido el número 0,17 en este intervalo, puede ser adecuado para representar "WIKI" comprimido. Por el contrario, si 0,16 o 0,1796875 no están en el intervalo, no encajarán y provocarán errores durante la decodificación.
Descompresión
Supongamos que recibimos el mensaje comprimido 0.17, así es como se decodificaría:
(Obviamente usamos la misma tabla que antes para conocer los intervalos de cada letra y sus probabilidades de aparición).
| Código comprimido | Intervalo | Carta correspondiente | Texto recuperado |
|---|---|---|---|
| 0,17 | [0; 0,25 [ | W | W |
| 0,68 | [0,25; 0,75 [ | I | Wisconsin |
| 0,86 | [0,75; 1 [ | K | WIK |
| 0,44 | [0,25; 0,75 [ | I | WIKI |
Por tanto, encontramos la cadena de caracteres correcta previamente comprimida.
Debilidades
Este método de compresión encuentra dos fallas principales que ahora se conocen y se corrigen:
- El primero es el hecho de utilizar una tabla de estadísticas fija, provocando los mismos problemas que para la codificación de Huffman, es decir, comprimir un archivo con estadísticas atípicas (los símbolos que deberían ser escasos están presentes). Se encuentran con alta probabilidad de ocurrencia). más grande después de la compresión que antes. La solución más eficaz es, por tanto, también en este caso, utilizar una tabla adaptativa cuyas frecuencias empiecen todas iguales en cada encuentro de un símbolo, cuyas estadísticas se actualizan y los intervalos se adaptan.
- El segundo gran problema es que, en términos de computadora, los números de coma son más complejos de manejar, pero pueden producir errores de redondeo (debido al número finito de dígitos después del punto decimal que puede soportar una computadora) que podrían resultar fatales durante la descompresión. Para superar este problema, es posible inicializar el intervalo de inicio con un límite inferior igual a 00000 ... y un límite superior igual a 99999 ... Los cálculos son los mismos que para números decimales pero en números enteros. Un nuevo problema puede seguir apareciendo cuando ambos terminales se acercan demasiado, por ejemplo . Este intervalo no contiene ningún valor entero y ninguna adición de nuevos símbolos lo modificará. Cuando lleguemos a este punto, debemos detener el algoritmo antes o, si los primeros dígitos tienen una diferencia entre ellos solo de 1 y el siguiente dígito vale 9 para el límite inferior y 0 para el superior, elimínelos primero. dígitos y mueva los siguientes dígitos a la izquierda. Los últimos dígitos serán entonces iguales a 0 para el límite inferior y 9 para el límite superior, lo que permite encontrar un nuevo número en este intervalo.
Artículos relacionados
Bibliografía
- (en) David MacKay, teoría de la información, inferencia y algoritmos de aprendizaje , Cambridge University Press ,2003( ISBN 0-521-64298-1 ) [ detalle de ediciones ]
Referencias
- Mark Nelson ( transl. Hervé Soulard), Compresión de datos: textos, imágenes y sonidos , Dunod ,1993, 421 p. ( ISBN 2-10-001681-4 )
- " COMPRESIÓN - compresión aritmética " (consultado el 17 de enero de 2015 )
- " Compresión de datos - Codificación aritmética " (consultado el 17 de enero de 2015 )
- " Capítulo 1: Codificación aritmética " (consultado el 18 de enero de 2015 )