Codificación aritmética

La codificación aritmética es una forma de codificación entrópica utilizado en compresión sin pérdidas. Normalmente, una cadena de caracteres está representada utilizando un número fijo de bits por carácter, como en el código ASCII. Cuándo una cadena es convertida a codificación aritmética, los caracteres frecuentemente usados serán almacenados con menos bits y los de uso menos habitual serán almacenados con más bits, resultando en menos bits utilizados en total. La codificación aritmética difiere de otras formas de codificación entrópica, como la codificación de Huffman, en que más que separar la entrada a símbolos componentes y reemplazar cada uno con un código, la codificación aritmética codifica el mensaje entero a un solo número, una fracción n dónde [0.0 ≤ ''n'' < 1.0).

Un ejemplo de codificación aritmética suponiendo una distribución de probabilidad fija de tres símbolos "A", "B" y "C". La probabilidad de "A" es 50%, la probabilidad de "B" es 33% y la probabilidad de "C" es 17%. Además asumimos que la profundidad de recursión es conocida en cada paso.
En el paso uno codificamos "B", el cual está dentro del intervalo [0.5, 0.83): el número binario "0.10x" es el código más corto que representa un intervalo que está enteramente dentro de [0.5, 0.83). "x" significa una secuencia de bits arbitraria. Hay dos casos extremos: la x más pequeña representa un número infinito de ceros, lo cual representa el lado izquierdo del intervalo representado. Luego el lado izquierdo del intervalo es dec(0.10) = 0.5. La x más grande representa un número infinito de unos lo cual da un número que converge hacia dec(0.11) = 0.75. Por lo tanto, "0.10x" representa el intervalo [0.5, 0.75) el cual está dentro de [0.5, 0.83).
Ahora podemos dejar la parte "0." puesto que todos los intervalos comienzan con  "0." y podemos ignorar la parte "x" porque no importa que secuencia de bits representa, nos mantenemos dentro de [0.5, 0.75).

Detalles de implementación y ejemplos

Probabilidades iguales

En el caso más simple, la probabilidad de aparición de 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. Un simple código de bloque requeriría 2 bits por símbolo, lo que es un desperdicio: una de las variaciones de bits nunca es usada. Es decir, A=00, B=01 y C=10, pero 11 no es usado.

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₃ (en la codificación aritmética los números están entre 0 y 1). El paso siguiente es codificar este número ternario usando un número binario de punto fijo con la suficiente precisión para recuperarlo, tal como 0.0010110010₂ - esto es sólo 10 bits; 2 bits son salvados en comparación con la codificación por bloque. Esto es factible para secuencias largas porque hay algoritmos eficientes para convertir la base de números precisos arbitrariamente.

Para decodificar el valor, conociendo que la cadena original tenía longitud 6, uno puede simplemente convertir de vuelta a base 3, redondear a 6 dígitos y recuperar la cadena.

Definiendo un modelo

En general, los codificadores aritméticos pueden producir una salida cerca del óptimo para cualquier conjunto de símbolos y probabilidades dado (el valor óptimo es -log₂P bits por cada símbolo de probabilidad P, vea teorema de codificación de fuentes). Los algoritmos de compresión que usan la codificación aritmética inician determinando un modelo de los datos - básicamente una predicción de que patrones serán encontrados en los símbolos del mensaje. Lo más acertada que sea la predicción, lo más cerca al óptimo que seá la salida.

Ejemplo: un simple modelo estático para describir la salida de un instrumento de monitoreo particular sobre el tiempo podría ser:

• 60% de probabilidad del símbolo NEUTRAL
• 20% de probabilidad del símbolo POSITIVE
• 10% de probabilidad del símbolo NEGATIVE
• 10% de probabilidad del símbolo END-OF-DATA (Fin de los datos). (La presencia de este símbolo significa que la transmisión será 'terminada internamente', como es bastante común en compresión de datos; cuando este símbolo aparece en el flujo de datos, el decodificador sabrá que el flujo entero ha sido decodificado.)

Los modelos también pueden manejar alfabetos diferentes al simple conjunto de cuatro símbolos escogido para este ejemplo. Modelos más sofisticados también son posibles: el modelado de alto-orden cambia su estimación de la probabilidad actual de un símbolo basado en los símbolos que le preceden (el contexto), así que en un modelo para texto en inglés, por ejemplo, el porcentaje de probabilidad de "u" sería mucho más alto cuando le sigue a una "Q" o a una "q". Los modelos pueden ser incluso adaptativos, de forma que continuamente cambian su predicción de los datos basados en lo que el flujo de datos contiene actualmente. El decodificador debe tener el mismo modelo que el codificador.

Codificación y decodificación: perspectiva general

En general, cada paso del proceso de codificación, excepto por el último, es el mismo; el codificador tiene básicamente sólo tres piezas de datos a considerar:

• El siguiente símbolo que necesita ser codificado.
• El intervalo actual (al inicio del proceso de codificación, el intervalo es [0,1], pero eso cambiará).
• Las probabilidades que el modelo asigna a cada uno de los varios símbolos que son posibles en esta etapa (como se mencionó antes, los modelos de alto-orden o adaptativos implican que estas probabilidades no son necesariamente las mismas en cada paso).

El codificador divide el intervalo actual en sub-intervalos, cada uno representando una fracción del actual intervalo proporcional a la probabilidad de ese símbolo en el contexto actual. Cualquiera que sea el intervalo que corresponda al símbolo actual que sigue a ser codificado se vuelve el intervalo usado en el siguiente paso.

Ejemplo: para el modelo de cuatro símbolos de arriba:

• el intervalo para NEUTRAL sería [0, 0.6)
• el intervalo para POSITIVE sería [0.6, 0.8)
• el intervalo para NEGATIVE sería [0.8, 0.9)
• el intervalo para END-OF-DATA sería [0.9, 1).

Cuando todos los símbolos hayan sido codificados, el intervalo resultante inequívocamente identifica la secuencia de símbolos que lo produjeron. Cualquiera que tenga el mismo intervalo final y el modelo que es usado puede reconstruir la secuencia de símbolos que debe haber sido ingresada al codificador para resultar en ese intervalo final.

No es necesario transmitir el intervalo final, sin embargo, es sólo necesario transmitir una fracción que cae dentro del intervalo. En particular, sólo es necesario transmitir suficientes dígitos (en cualquier base) de la fracción de forma que todas las fracciones que comienzan con esos dígitos caigan dentro del intervalo final; esto garantizará que el código resultante es un código prefijo.

Codificación y decodificación: ejemplo

 

Un diagrama mostrando la decodificación de 0.538 (el punto circular) en el modelo de ejemplo. La región es dividida en subregiones proporcionales a las frecuencias de los símbolos, luego la subregión que contiene el punto es sucesivamente subdividida de la misma forma.

Considere el proceso para decodificar un mensaje codificado con el modelo de cuatro símbolos dado. El mensaje es codificado en la fracción 0.538 (usando decimal para claridad, en lugar de binario; también asumiendo que hay sólo tantos dígitos como se necesitan para decodificar el mensaje).

El proceso inicia con el mismo intervalo por el decodificador: [0,1), y usando el mismo modelo, dividiéndolo en los mismos cuatro sub-intervalos que el codificador debe tener. La fracción 0.538 cae dentro del sub-intervalo para NEUTRAL, [0, 0.6); esto indica que el primer símbolo que el codificador debe haber leído ha sido NEUTRAL, entonces este es el primer símbolo del mensaje.

Luego divida el intervalo [0, 0.6) en sub-intervalos:

• el intervalo para NEUTRAL sería [0, 0.36), 60% de [0, 0.6).
• el intervalo para POSITIVE sería [0.36, 0.48), 20% de [0, 0.6).
• el intervalo para NEGATIVE sería [0.48, 0.54), 10% de [0, 0.6).
• el intervalo para END-OF-DATA sería [0.54, 0.6), 10% de [0, 0.6).

Puesto que 0.538 está dentro del intervalo [0.48, 0.54), el segundo símbolo del mensaje debe haber sido NEGATIVE.

Otra vez divida nuestro intervalo en sub-intervalos:

• el intervalo para NEUTRAL sería [0.48, 0.516).
• el intervalo para POSITIVE sería [0.516, 0.528).
• el intervalo para NEGATIVE sería [0.528, 0.534).
• el intervalo para END-OF-DATA sería [0.534, 0.540).

Ahora 0.538 cae dentro del intervalo del símbolo END-OF-DATA; por lo tanto, éste debe ser el siguiente símbolo. Puesto que es también el símbolo de terminación, quiere decir que la decodificación está completa. Si el flujo de datos no está terminado internamente, se necesita otra forma de indicar cuando el flujo se detiene. De otra forma, el proceso de decodificación podría continuar por siempre, erróneamente leyendo más símbolos de la fracción de los que fueron codificados en ella.

•   Datos: Q2651