Codificación aritmética
La codificación aritmética ( AC ) es una forma de codificación de entropía utilizada en la compresión de datos sin pérdidas . Normalmente, una cadena de caracteres se representa mediante un número fijo de bits por carácter, como en el código ASCII . Cuando una cadena se convierte a codificación aritmética, los caracteres de uso frecuente se almacenarán con menos bits y los caracteres que ocurren con menos frecuencia se almacenarán con más bits, lo que resultará en un menor uso de bits en total. La codificación aritmética difiere de otras formas de codificación de entropía, como la codificación de Huffman., en que en lugar de separar la entrada en símbolos componentes y reemplazar cada uno con un código, la codificación aritmética codifica todo el mensaje en un solo número, una fracción de precisión arbitraria q , donde 0.0 ≤ q <1.0 . Representa la información actual como un rango, definido por dos números. [1] Una familia reciente de codificadores de entropía llamados sistemas numéricos asimétricos permite implementaciones más rápidas gracias a que operan directamente en un solo número natural que representa la información actual. [2]
En el caso más simple, la probabilidad de que ocurra cada símbolo es igual. Por ejemplo, considere un conjunto de tres símbolos, A, B y C, cada uno con la misma probabilidad de ocurrir. La codificación de bloques simple requeriría 2 bits por símbolo, lo cual es un desperdicio: una de las variaciones de bits nunca se usa. Es decir, los símbolos A, B y C pueden codificarse respectivamente como 00, 01 y 10, con 11 sin usar.
Una solución más eficiente es representar una secuencia de estos tres símbolos como un número racional en base 3 donde cada dígito representa un símbolo. Por ejemplo, la secuencia "ABBCAB" podría convertirse en 0.011201 3 , en codificación aritmética como un valor en el intervalo [0, 1). El siguiente paso es codificar este número ternario usando un número binario de coma fija de suficiente precisión para recuperarlo, como 0.0010110010 2 - esto es solo 10 bits; Se guardan 2 bits en comparación con la codificación de bloques ingenua. Esto es factible para secuencias largas porque existen algoritmos eficientes en el lugar para convertir la base de números arbitrariamente precisos.
Para decodificar el valor, sabiendo que la cadena original tenía una longitud de 6, uno puede simplemente convertir de nuevo a base 3, redondear a 6 dígitos y recuperar la cadena.
En general, los codificadores aritméticos pueden producir resultados casi óptimos para cualquier conjunto dado de símbolos y probabilidades. (El valor óptimo es −log 2 P bits para cada símbolo de probabilidad P ; consulte el teorema de codificación de fuente ). Los algoritmos de compresión que usan codificación aritmética comienzan determinando un modelo de los datos, básicamente una predicción de qué patrones se encontrarán en los símbolos. del mensaje. Cuanto más precisa sea esta predicción, más cerca del resultado óptimo estará.
Ejemplo : un modelo estático simple para describir la salida de un instrumento de monitoreo particular a lo largo del tiempo podría ser:
| 1. | Se encuentran las frecuencias de las letras. |
|---|---|
| 2. | El intervalo [0, 1) se divide en la relación de las frecuencias. |
| 3-5. | El intervalo correspondiente se divide de forma iterativa para cada letra del mensaje. |
| 6. | Se elige cualquier valor en el intervalo final para representar el mensaje. |
| 2 * –6 *. | La partición y el valor si el mensaje fuera "KIWI" en su lugar. |
