Codificación aritmética - Arithmetic coding

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 dará como resultado que se utilicen menos bits en total. La codificación aritmética se diferencia 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 q de precisión arbitraria , donde 0.0 ≤ q <1.0 . Representa la información actual como un rango, definido por dos números. 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.

Un ejemplo de codificación aritmética que supone una distribución de probabilidad fija de tres símbolos "A", "B" y "C". La probabilidad de "A" es del 50%, la probabilidad de "B" es del 33% y la probabilidad de "C" es del 17%. Además, asumimos que la profundidad de recursividad se conoce en cada paso. En el paso uno codificamos "B" que está dentro del intervalo [0.5, 0.83): El número binario "0.10 x " es el código más corto que representa un intervalo que está completamente dentro de [0.5, 0.83). " x " significa una secuencia de bits arbitraria. Hay dos casos extremos: la x más pequeña representa cero, que representa el lado izquierdo del intervalo representado. Entonces el lado izquierdo del intervalo es dec (0.10) = 0.5. En el otro extremo, x representa una secuencia finita de unos que tiene el límite superior dec (0,11) = 0,75. Por lo tanto, "0.10 x " representa el intervalo [0.5, 0.75) que está dentro de [0.5, 0.83). Ahora podemos omitir el "0". parte ya que todos los intervalos comienzan con "0". y podemos ignorar la parte " x " porque no importa qué secuencia de bits representa, permaneceremos dentro de [0.5, 0.75).

Detalles y ejemplos de implementación

Codificación del mensaje "WIKI" con codificación aritmética

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.

El ejemplo anterior se visualiza como un círculo, los valores en rojo codifican "WIKI" y "KIWI" - en la imagen SVG , coloque el cursor sobre un intervalo para resaltarlo y mostrar sus estadísticas

Igualdad de probabilidades

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 ₃ , 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 ₂ - 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.

Definiendo un modelo

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 ₂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 cercana será la salida óptima.

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

60% de probabilidad de símbolo NEUTRO
20% de probabilidad de símbolo POSITIVO
10% de probabilidad de símbolo NEGATIVO
10% de probabilidad de símbolo END-OF-DATA. (La presencia de este símbolo significa que el flujo se 'terminará internamente', como es bastante común en la compresión de datos; cuando este símbolo aparece en el flujo de datos, el decodificador sabrá que se ha decodificado todo el flujo).

Los modelos también pueden manejar alfabetos distintos al conjunto simple de cuatro símbolos elegido para este ejemplo. También son posibles modelos más sofisticados: el modelado de orden superior cambia su estimación de la probabilidad actual de un símbolo en función de los símbolos que lo preceden (el contexto ), de modo que en un modelo para texto en inglés, por ejemplo, el porcentaje de probabilidad de " u "sería mucho mayor cuando sigue una" Q "o una" q ". Los modelos pueden incluso ser adaptables , de modo que cambian continuamente su predicción de los datos en función de lo que realmente contiene la transmisión. El decodificador debe tener el mismo modelo que el codificador.

Codificación y decodificación: descripción general

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

El siguiente símbolo que debe codificarse
El intervalo actual (al comienzo del proceso de codificación, el intervalo se establece en [0,1], pero eso cambiará)
Las probabilidades que el modelo asigna a cada uno de los diversos símbolos que son posibles en esta etapa (como se mencionó anteriormente, los modelos adaptativos o de orden superior significan que estas probabilidades no son necesariamente las mismas en cada paso).

El codificador divide el intervalo actual en subintervalos, cada uno de los cuales representa una fracción del intervalo actual proporcional a la probabilidad de ese símbolo en el contexto actual. El intervalo que corresponda al símbolo real que se codificará a continuación se convierte en el intervalo utilizado en el siguiente paso.

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

el intervalo para NEUTRO sería [0, 0.6)
el intervalo para POSITIVO sería [0.6, 0.8)
el intervalo para NEGATIVO sería [0.8, 0.9)
el intervalo para FIN DE DATOS sería [0.9, 1).

Cuando todos los símbolos han sido codificados, el intervalo resultante identifica sin ambigüedades la secuencia de símbolos que lo produjeron. Cualquiera que tenga el mismo intervalo final y modelo que se está utilizando puede reconstruir la secuencia de símbolos que debe haber ingresado al codificador para dar como resultado ese intervalo final.

Sin embargo, no es necesario transmitir el intervalo final; solo es necesario transmitir una fracción que se encuentre dentro de ese intervalo. En particular, solo es necesario transmitir suficientes dígitos (en cualquier base) de la fracción para que todas las fracciones que comiencen con esos dígitos caigan en el intervalo final; esto garantizará que el código resultante sea un código de prefijo .

Codificación y decodificación: ejemplo

Un diagrama que muestra la decodificación de 0.538 (el punto redondo) en el modelo de ejemplo. La región se divide en subregiones proporcionales a las frecuencias de los símbolos, luego la subregión que contiene el punto se subdivide sucesivamente de la misma manera.

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

El proceso comienza con el mismo intervalo que utiliza el codificador: [0,1), y utilizando el mismo modelo, dividiéndolo en los mismos cuatro subintervalos que debe tener el codificador. La fracción 0,538 cae en el subintervalo de NEUTRO, [0, 0,6); esto indica que el primer símbolo que leyó el codificador debe haber sido NEUTRO, por lo que este es el primer símbolo del mensaje.

A continuación, divida el intervalo [0, 0,6) en subintervalos:

el intervalo para NEUTRO sería [0, 0,36), 60% de [0, 0,6) .
el intervalo para POSITIVO sería [0.36, 0.48), 20% de [0, 0.6) .
el intervalo para NEGATIVO sería [0.48, 0.54), 10% de [0, 0.6) .
el intervalo para FIN DE DATOS sería [0.54, 0.6), 10% de [0, 0.6) .

Dado que 0,538 está dentro del intervalo [0,48, 0,54), el segundo símbolo del mensaje debe haber sido NEGATIVO.

Nuevamente, divida nuestro intervalo actual en subintervalos:

el intervalo para NEUTRO sería [0,48, 0,516).
el intervalo para POSITIVO sería [0.516, 0.528).
el intervalo para NEGATIVO sería [0.528, 0.534).
el intervalo para FIN DE DATOS sería [0.534, 0.540).

Ahora 0.538 cae dentro del intervalo del símbolo FIN DE DATOS; por lo tanto, este debe ser el siguiente símbolo. Dado que también es el símbolo de terminación interno, significa que la decodificación está completa. Si la transmisión no se termina internamente, debe haber alguna otra forma de indicar dónde se detiene la transmisión. De lo contrario, el proceso de decodificación podría continuar para siempre, leyendo por error más símbolos de la fracción de los que de hecho se codificaron en ella.

Fuentes de ineficiencia

El mensaje 0.538 en el ejemplo anterior podría haber sido codificado por las fracciones igualmente cortas 0.534, 0.535, 0.536, 0.537 o 0.539. Esto sugiere que el uso de decimal en lugar de binario introdujo cierta ineficiencia. Esto es correcto; el contenido de información de un decimal de tres dígitos son bits ; el mismo mensaje podría haber sido codificado en la fracción binaria 0.10001010 (equivalente a 0.5390625 decimal) a un costo de solo 8 bits. (El cero final debe especificarse en la fracción binaria, de lo contrario, el mensaje sería ambiguo sin información externa, como el tamaño de la secuencia comprimida). ${\ Displaystyle 3 * \ log _ {2} (10) \ approx 9.966}$

Esta salida de 8 bits es mayor que el contenido de información o la entropía del mensaje, que es

{\ Displaystyle \ sum - \ log _ {2} (p_ {i}) = - \ log _ {2} (0.6) - \ log _ {2} (0.1) - \ log _ {2} (0.1) = 7.381 {\ text {bits}}}

Pero se debe usar un número entero de bits en la codificación binaria, por lo que un codificador para este mensaje usaría al menos 8 bits, lo que da como resultado un mensaje 8.4% más grande que el contenido de la entropía. Esta ineficacia de 1 bit como máximo da como resultado una sobrecarga relativamente menor a medida que aumenta el tamaño del mensaje.

Además, las probabilidades de símbolo reivindicadas fueron [0,6, 0,2, 0,1, 0,1), pero las frecuencias reales en este ejemplo son [0,33, 0, 0,33, 0,33). Si se reajustan los intervalos para estas frecuencias, la entropía del mensaje sería de 4,755 bits y el mismo mensaje de FIN DE DATOS NEGATIVO NEUTRO podría codificarse como intervalos [0, 1/3); [1/9, 2/9); [27/5, 27/6); y un intervalo binario de [0,00101111011, 0,00111000111). Este es también un ejemplo de cómo los métodos de codificación estadística como la codificación aritmética pueden producir un mensaje de salida que es más grande que el mensaje de entrada, especialmente si el modelo de probabilidad está desactivado.

Codificación aritmética adaptativa

Una ventaja de la codificación aritmética sobre otros métodos similares de compresión de datos es la conveniencia de la adaptación. La adaptación es el cambio de las tablas de frecuencia (o probabilidad) mientras se procesan los datos. Los datos decodificados coinciden con los datos originales siempre que la tabla de frecuencias en la decodificación se reemplace de la misma manera y en el mismo paso que en la codificación. Normalmente, la sincronización se basa en una combinación de símbolos que se producen durante el proceso de codificación y decodificación.

Precisión y renormalización

Las explicaciones anteriores de la codificación aritmética contienen cierta simplificación. En particular, se escriben como si el codificador calculara primero las fracciones que representan los puntos finales del intervalo en su totalidad, utilizando una precisión infinita , y solo convirtiera la fracción a su forma final al final de la codificación. En lugar de intentar simular una precisión infinita, la mayoría de los codificadores aritméticos operan con un límite fijo de precisión que saben que el decodificador podrá igualar y redondear las fracciones calculadas a sus equivalentes más cercanos con esa precisión. Un ejemplo muestra cómo funcionaría esto si el modelo pidiera que el intervalo $[0,1)$ se dividiera en tercios, y esto se aproximó con una precisión de 8 bits. Tenga en cuenta que, dado que ahora se conoce la precisión, también lo son los rangos binarios que podremos usar.

Símbolo	Probabilidad	Intervalo reducido a precisión de ocho bits		Abarcar
Símbolo	(expresado como fracción)	(como fracciones)	(en binario)	(en binario)
A	1/3	$[0, 85/256)$	[0.00000000, 0.01010101)	00000000-01010100
B	1/3	$[85/256, 171/256)$	[0.01010101, 0.10101011)	01010101-10101010
C	1/3	$[171/256, 1)$	[0.10101011, 1.00000000)	10101011-11111111

Un proceso llamado renormalización evita que la precisión finita se convierta en un límite en el número total de símbolos que se pueden codificar. Siempre que el rango se reduce al punto en el que todos los valores en el rango comparten ciertos dígitos iniciales, esos dígitos se envían a la salida. Por muchos dígitos de precisión que pueda manejar la computadora , ahora maneja menos, por lo que los dígitos existentes se desplazan hacia la izquierda y, a la derecha, se agregan nuevos dígitos para expandir el rango lo más ampliamente posible. Tenga en cuenta que este resultado ocurre en dos de los tres casos de nuestro ejemplo anterior.

Símbolo	Probabilidad	Abarcar	Dígitos que se pueden enviar a la salida	Rango después de la renormalización
A	1/3	0 0000000 - 0 1,0101 millones	0	0000000 0 - 1010100 1
B	1/3	01010101-10101010	Ninguno	01010101-10101010
C	1/3	1 0101011 - 1 1111111	1	0101011 0 - 1,111111 millones 1

Codificación aritmética como cambio generalizado de base

Recuerde que en el caso de que los símbolos tuvieran probabilidades iguales, la codificación aritmética podría implementarse mediante un simple cambio de base o raíz. En general, la codificación aritmética (y de rango) se puede interpretar como un cambio generalizado de base . Por ejemplo, podemos mirar cualquier secuencia de símbolos:

{\ Displaystyle \ mathrm {DABDDB}}

como un número en una cierta base suponiendo que los símbolos involucrados forman un conjunto ordenado y cada símbolo en el conjunto ordenado denota un entero secuencial A = 0, B = 1, C = 2, D = 3, y así sucesivamente. Esto da como resultado las siguientes frecuencias y frecuencias acumuladas:

Símbolo	Frecuencia de ocurrencia	Frecuencia acumulada
A	1	0
B	2	1
D	3	3

La frecuencia acumulada de un elemento es la suma de todas las frecuencias que preceden al elemento. En otras palabras, la frecuencia acumulada es un total acumulado de frecuencias.

En un sistema numérico posicional , la raíz, o base, es numéricamente igual a varios símbolos diferentes utilizados para expresar el número. Por ejemplo, en el sistema decimal el número de símbolos es 10, a saber, 0, 1, 2, 3, 4, 5, 6, 7, 8 y 9. La base se usa para expresar cualquier entero finito en un supuesto multiplicador en forma polinomial. Por ejemplo, el número 457 es en realidad 4 × 10 ² + 5 × 10 ¹ + 7 × 10 ⁰ , donde se presume la base 10 pero no se muestra explícitamente.

Inicialmente, convertiremos DABDDB en un número de base 6, porque 6 es la longitud de la cadena. La cadena se asigna primero a la cadena de dígitos 301331, que luego se asigna a un número entero por el polinomio:

{\ Displaystyle 6 ^ {5} \ times 3 + 6 ^ {4} \ times 0 + 6 ^ {3} \ times 1 + 6 ^ {2} \ times 3 + 6 ^ {1} \ times 3 + 6 ^ {0} \ times 1 = 23671}

El resultado 23671 tiene una longitud de 15 bits, que no se acerca mucho al límite teórico (la entropía del mensaje), que es de aproximadamente 9 bits.

Para codificar un mensaje con una longitud más cercana al límite teórico impuesto por la teoría de la información, necesitamos generalizar ligeramente la fórmula clásica para cambiar la base. Calcularemos los límites superior e inferior L y U y elegiremos un número entre ellos. Para el cálculo de L , multiplicamos cada término en la expresión anterior por el producto de las frecuencias de todos los símbolos ocurridos anteriormente:

{\ Displaystyle {\ begin {alineado} L = {} & (6 ^ {5} \ times 3) + {} \\ & 3 \ times (6 ^ {4} \ times 0) + {} \\ & (3 \ times 1) \ times (6 ^ {3} \ times 1) + {} \\ & (3 \ times 1 \ times 2) \ times (6 ^ {2} \ times 3) + {} \\ & ( 3 \ times 1 \ times 2 \ times 3) \ times (6 ^ {1} \ times 3) + {} \\ & (3 \ times 1 \ times 2 \ times 3 \ times 3) \ times (6 ^ { 0} \ times 1) {} \\ = {} & 25002 \ end {alineado}}}

La diferencia entre este polinomio y el polinomio anterior es que cada término se multiplica por el producto de las frecuencias de todos los símbolos que aparecen anteriormente. De manera más general, L se puede calcular como:

{\ Displaystyle L = \ sum _ {i = 1} ^ {n} n ^ {ni} C_ {i} {\ prod _ {k = 1} ^ {i-1} f_ {k}}}

donde son las frecuencias acumuladas y son las frecuencias de ocurrencias. Los índices denotan la posición del símbolo en un mensaje. En el caso especial en el que todas las frecuencias son 1, esta es la fórmula de cambio de base. ${\ Displaystyle \ scriptstyle C_ {i}}$ ${\ Displaystyle \ scriptstyle f_ {k}}$ ${\ Displaystyle \ scriptstyle f_ {k}}$

El límite superior U será L más el producto de todas las frecuencias; en este caso U = L + (3 × 1 × 2 × 3 × 3 × 2) = 25002 + 108 = 25110. En general, U viene dado por:

{\ Displaystyle U = L + \ prod _ {k = 1} ^ {n} f_ {k}}

Ahora podemos elegir cualquier número del intervalo [ L , U ) para representar el mensaje; una opción conveniente es el valor con el rastro de ceros más largo posible, 25100, ya que nos permite lograr la compresión al representar el resultado como 251 × 10 ² . Los ceros también se pueden truncar, dando 251, si la longitud del mensaje se almacena por separado. Los mensajes más largos tenderán a tener rastros más largos de ceros.

Para decodificar el número entero 25100, el cálculo del polinomio se puede invertir como se muestra en la siguiente tabla. En cada etapa se identifica el símbolo actual, luego el término correspondiente se resta del resultado.

Recordatorio	Identificación	Símbolo identificado	Resto corregido
25100	25100/6 ⁵ = 3	D	(25100 - 6 ⁵ × 3) / 3 = 590
590	590/6 ⁴ = 0	A	(590 - 6 ⁴ × 0) / 1 = 590
590	590/6 ³ = 2	B	(590 - 6 ³ × 1) / 2 = 187
187	187/6 ² = 5	D	(187 - 6 ² × 3) / 3 = 26
26	26/6 ¹ = 4	D	(26 - 6 ¹ × 3) / 3 = 2
2	2/6 ⁰ = 2	B	-

Durante la decodificación, tomamos la palabra después de dividir por la potencia correspondiente de 6. El resultado se compara con los intervalos acumulativos y se selecciona el símbolo apropiado de la tabla de consulta. Cuando se identifica el símbolo, se corrige el resultado. El proceso continúa durante la longitud conocida del mensaje o mientras el resultado restante es positivo. La única diferencia en comparación con el cambio de base clásico es que puede haber un rango de valores asociados con cada símbolo. En este ejemplo, A es siempre 0, B es 1 o 2, y D es cualquiera de 3, 4, 5. Esto está exactamente de acuerdo con nuestros intervalos que están determinados por las frecuencias. Cuando todos los intervalos son iguales a 1, tenemos un caso especial del clásico cambio de base.

Límite teórico de mensaje comprimido

El límite inferior L nunca excede n ⁿ , donde n es el tamaño del mensaje, por lo que se puede representar en bits. Después del cálculo del límite superior U y la reducción del mensaje seleccionando un número del intervalo [ L , U ) con el rastro más largo de ceros, podemos suponer que esta longitud se puede reducir en bits. Dado que cada frecuencia en un producto ocurre exactamente el mismo número de veces que el valor de esta frecuencia, podemos usar el tamaño del alfabeto A para el cálculo del producto ${\ Displaystyle \ scriptstyle \ log _ {2} (n ^ {n}) \; = \; n \ log _ {2} (n)}$ ${\ Displaystyle \ scriptstyle \ log _ {2} \ left (\ prod _ {k = 1} ^ {n} f_ {k} \ right)}$

{\ Displaystyle \ prod _ {k = 1} ^ {n} f_ {k} = \ prod _ {k = 1} ^ {A} f_ {k} ^ {f_ {k}}}

Aplicando log ₂ para el número estimado de bits en el mensaje, el mensaje final (sin contar una sobrecarga logarítmica para las tablas de longitud y frecuencia del mensaje) coincidirá con el número de bits dado por la entropía , que para mensajes largos es muy cercano al óptimo:

{\ Displaystyle - \ left [\ sum _ {i = 1} ^ {A} f_ {i} \ log _ {2} (f_ {i}) \ right] * n}

Conexiones con otros métodos de compresión

Codificación Huffman

Debido a que la codificación aritmética no comprime un dato a la vez, puede acercarse arbitrariamente a la entropía al comprimir cadenas iid . Por el contrario, el uso de la extensión de la codificación de Huffman (a cadenas) no alcanza la entropía a menos que todas las probabilidades de los símbolos del alfabeto sean potencias de dos, en cuyo caso tanto la codificación de Huffman como la aritmética logran la entropía.

Cuando Huffman codifica ingenuamente cadenas binarias, no es posible la compresión, incluso si la entropía es baja (por ejemplo, ({0, 1}) tiene probabilidades {0.95, 0.05}). La codificación de Huffman asigna 1 bit a cada valor, lo que da como resultado un código de la misma longitud que la entrada. Por el contrario, la codificación aritmética comprime bien los bits, acercándose a la relación de compresión óptima de

{\ Displaystyle 1 - [- 0,95 \ log _ {2} (0,95) + - 0,05 \ log _ {2} (0,05)] \ aproximadamente 71,4 \%.}

Una forma sencilla de abordar la subóptimaidad de la codificación de Huffman es concatenar símbolos ("bloqueo") para formar un nuevo alfabeto en el que cada nuevo símbolo representa una secuencia de símbolos originales, en este caso bits, del alfabeto original. En el ejemplo anterior, agrupar secuencias de tres símbolos antes de la codificación produciría nuevos "super-símbolos" con las siguientes frecuencias:

000: 85,7%
001, 010, 100: 4.5% cada uno
011, 101, 110: 0,24% cada uno
111: 0,0125%

Con esta agrupación, la codificación de Huffman promedia 1,3 bits por cada tres símbolos, o 0,433 bits por símbolo, en comparación con un bit por símbolo en la codificación original, es decir, compresión. Permitir secuencias arbitrariamente grandes se acerca arbitrariamente a la entropía, al igual que la codificación aritmética, pero requiere códigos enormes para hacerlo, por lo que no es tan práctico como la codificación aritmética para este propósito. ${\ Displaystyle 56,7 \%}$

Una alternativa es codificar longitudes de ejecución mediante códigos Golomb-Rice basados en Huffman . Este enfoque permite una codificación / decodificación más simple y rápida que la codificación aritmética o incluso la codificación Huffman, ya que esta última requiere búsquedas en una tabla. En el ejemplo {0.95, 0.05}, un código de Golomb-Rice con un resto de cuatro bits logra una relación de compresión mucho más cercana al óptimo que con bloques de tres bits. Sin embargo, los códigos de Golomb-Rice solo se aplican a entradas de Bernoulli como la de este ejemplo, por lo que no sustituye al bloqueo en todos los casos. ${\ Displaystyle 71,1 \%}$

Historia y patentes

Los algoritmos básicos para la codificación aritmética fueron desarrollados de forma independiente por Jorma J. Rissanen , en IBM Research , y por Richard C. Pasco, un Ph.D. estudiante de la Universidad de Stanford ; ambos fueron publicados en mayo de 1976. Pasco cita un borrador previo a la publicación del artículo de Rissanen y comenta la relación entre sus trabajos:

Un algoritmo de la familia fue desarrollado de forma independiente por Rissanen [1976]. Desplaza el elemento de código al extremo más significativo del acumulador, utilizando un puntero obtenido por suma y exponenciación. Ahora compararemos las alternativas en las tres opciones y veremos que es preferible cambiar el elemento de código en lugar del acumulador y agregar elementos de código al extremo menos significativo del acumulador.

Menos de un año después de la publicación, IBM solicitó una patente estadounidense sobre el trabajo de Rissanen. El trabajo de Pasco no fue patentado.

Históricamente, las patentes estadounidenses han cubierto una variedad de técnicas específicas para la codificación aritmética, aunque desde entonces varios métodos bien conocidos han pasado al dominio público cuando las patentes han expirado. Las técnicas cubiertas por patentes pueden ser esenciales para implementar los algoritmos de codificación aritmética que se especifican en algunos estándares internacionales formales. Cuando este es el caso, tales patentes están generalmente disponibles para licencia bajo lo que se llama términos de licencia "razonables y no discriminatorios" ( RAND ) (al menos como una cuestión de política del comité de estándares). En algunos casos bien conocidos (incluidos algunos relacionados con patentes de IBM que han expirado desde entonces), dichas licencias estaban disponibles de forma gratuita y, en otros casos, se han exigido tarifas de licencia. La disponibilidad de licencias bajo los términos de RAND no satisface necesariamente a todos los que quieran utilizar la tecnología, ya que lo que puede parecer "razonable" para una empresa que prepara un producto de software comercial propietario puede parecer mucho menos razonable para un proyecto de software libre o de código abierto.

Al menos un programa de software de compresión importante, bzip2 , suspendió deliberadamente el uso de la codificación aritmética a favor de la codificación Huffman debido a la situación de patentes percibida en ese momento. Además, los codificadores y decodificadores del formato de archivo JPEG , que tiene opciones tanto para la codificación Huffman como para la codificación aritmética, generalmente solo admiten la opción de codificación Huffman, que originalmente se debió a problemas de patentes; el resultado es que casi todas las imágenes JPEG que se utilizan actualmente utilizan codificación Huffman, aunque las patentes de codificación aritmética de JPEG han expirado debido a la antigüedad del estándar JPEG (cuyo diseño se completó aproximadamente en 1990). JPEG XL , así como archivadores como PackJPG, Brunsli y Lepton, que pueden convertir sin pérdidas archivos codificados con Huffman a archivos con codificación aritmética (o sistemas numéricos asimétricos en el caso de JPEG XL), mostrando hasta un 25% de ahorro de tamaño.

El algoritmo de codificación aritmética del formato de compresión de imágenes JPEG se basa en las siguientes patentes citadas (desde que expiraron).

Patente de EE . UU . 4.652.856 - ( IBM ) Presentada el 4 de febrero de 1986, concedida el 24 de marzo de 1987 - Kottappuram MA Mohiuddin, Jorma Johannen Rissanen - Código aritmético de varios alfabetos sin multiplicación
Patente de los Estados Unidos 4,905,297 - (IBM) Presentada el 18 de noviembre de 1988, concedida el 27 de febrero de 1990 - Glen George Langdon, Joan L. Mitchell, William B. Pennebaker, Jorma Johannen Rissanen - Sistema de codificación y descodificación de codificación aritmética
Patente de Estados Unidos 4.935.882 - (IBM) Presentada el 20 de julio de 1988, concedida el 19 de junio de 1990 - William B. Pennebaker, Joan L. Mitchell - Adaptación de probabilidad para codificadores aritméticos
Patente JP 1021672 - ( Mitsubishi ) presentada el 21 de enero de 1989, concedida el 10 de agosto de 1990 - Toshihiro Kimura, Shigenori Kino, Fumitaka Ono, Masayuki Yoshida - Sistema de codificación
Patente JP 2-46275 - (Mitsubishi) presentada el 26 de febrero de 1990, concedida el 5 de noviembre de 1991 - Fumitaka Ono, Tomohiro Kimura, Masayuki Yoshida, Shigenori Kino - Aparato de codificación y método de codificación

Otras patentes (en su mayoría también vencidas) relacionadas con la codificación aritmética incluyen las siguientes.

Patente de Estados Unidos 4.122.440 - (IBM) Presentada el 4 de marzo de 1977, concedida el 24 de octubre de 1978 - Glen George Langdon, Jorma Johannen Rissanen - Método y medios para la codificación aritmética de cadenas
Patente de Estados Unidos 4.286.256 - (IBM) Presentada el 28 de noviembre de 1979, concedida el 25 de agosto de 1981 - Glen George Langdon, Jorma Johannen Rissanen - Método y medios para la codificación aritmética utilizando un número reducido de operaciones
Patente de EE . UU . 4.467.317 - (IBM) Presentada el 30 de marzo de 1981, concedida el 21 de agosto de 1984 - Glen George Langdon, Jorma Johannen Rissanen - Codificación de compresión aritmética de alta velocidad utilizando actualización de valor concurrente
Patente de EE.UU. 4.891.643 - (IBM) Presentada el 15 de septiembre de 1986, concedida el 2 de enero de 1990 - Joan L. Mitchell, William B. Pennebaker - Compresión / descompresión de datos de codificación aritmética mediante codificadores y decodificadores de codificación aritmética diversos empleados selectivamente
Patente JP 11782787 - ( NEC ) Presentada el 13 de mayo de 1987, concedida el 18 de noviembre de 1988 - Michio Shimada - Dispositivo de codificación aritmética de compresión de datos
Patente JP 15015487 - ( KDDI ) Presentada el 18 de junio de 1987, concedida el 22 de diciembre de 1988 - Shuichi Matsumoto, Masahiro Saito - Sistema para prevenir la propagación portadora en codificación aritmética
Patente de Estados Unidos 4.933.883 - (IBM) Presentada el 3 de mayo de 1988, concedida el 12 de junio de 1990 - William B. Pennebaker, Joan L. Mitchell - Adaptación de probabilidad para codificadores aritméticos
Patente de Estados Unidos 4.989.000 - (IBM) Presentada el 19 de junio de 1989, concedida el 29 de enero de 1991 - Dan S. Chevion, Ehud D. Karnin, Eugeniusz Walach - Compresión de cadenas de datos mediante codificación aritmética con estimación de subintervalos de probabilidad simplificada
Patente de Estados Unidos 5.099.440 - (IBM) Presentada el 5 de enero de 1990, concedida el 24 de marzo de 1992 - William B. Pennebaker, Joan L. Mitchell - Adaptación de probabilidad para codificadores aritméticos
Patente de Estados Unidos 5.272.478 - ( Ricoh ) Presentada el 17 de agosto de 1992, concedida el 21 de diciembre de 1993 - James D. Allen - Método y aparato para la codificación de entropía

Nota: esta lista no es exhaustiva. Consulte los siguientes enlaces para obtener una lista de más patentes de EE. UU. El códec Dirac utiliza codificación aritmética y no tiene patente pendiente.

Pueden existir patentes de codificación aritmética en otras jurisdicciones; consulte las patentes de software para obtener más información sobre la patentabilidad del software en todo el mundo.

Benchmarks y otras características técnicas

Cada implementación programática de codificación aritmética tiene una relación de compresión y un rendimiento diferentes. Si bien las tasas de compresión varían solo un poco (generalmente menos del 1%), el tiempo de ejecución del código puede variar en un factor de 10. Elegir el codificador correcto de una lista de codificadores disponibles públicamente no es una tarea simple porque el rendimiento y la tasa de compresión también dependen de el tipo de datos, particularmente sobre el tamaño del alfabeto (número de símbolos diferentes). Uno de los dos codificadores en particular puede tener un mejor rendimiento para alfabetos pequeños, mientras que el otro puede mostrar un mejor rendimiento para alfabetos grandes. La mayoría de los codificadores tienen limitaciones en el tamaño del alfabeto y muchos de ellos están especializados para alfabetos de exactamente dos símbolos (0 y 1).

Ver también

Notas

^ Ze-Nian Li; Mark S. Drew; Jiangchuan Liu (9 de abril de 2014). Fundamentos de Multimedia . Springer Science & Business Media. ISBN 978-3-319-05290-8.
^ J. Duda, K. Tahboub, NJ Gadil, EJ Delp, El uso de sistemas numéricos asimétricos como un reemplazo preciso para la codificación de Huffman , Simposio de codificación de imágenes, 2015.
^ Richard Clark Pasco, "Algoritmos de codificación de origen para la compresión rápida de datos", Ph.D. disertación, Stanford Univ., mayo de 1976.
^ [1] ¿Qué es JPEG? Comp.compression Preguntas frecuentes (parte 1/3)
^ "Recomendación T.81 (1992) Corrigendum 1 (04/01)" . Recomendación T.81 (1992) . Unión Internacional de Telecomunicaciones. 9 de noviembre de 2004 . Consultado el 3 de febrero de 2011 .
^ Estándar de compresión de datos de imagen fija JPEG , WB Pennebaker y JL Mitchell , Kluwer Academic Press, 1992. ISBN 0-442-01272-1
^ "T.81 - COMPRESIÓN DIGITAL Y CODIFICACIÓN DE IMÁGENES FIJAS EN TONO CONTINUO - REQUISITOS Y DIRECTRICES" (PDF) . CCITT . Septiembre de 1992 . Consultado el 12 de julio de 2019 .
^ [2] Comp.compression Preguntas frecuentes (parte 1/3)
^ [3] Lanzamiento del códec de vídeo 1.0 de Dirac
^ Por ejemplo, Howard y Vitter (1994) discuten versiones de codificación aritmética basadas en rangos de números reales, aproximaciones enteras a esos rangos y un tipo de aproximación aún más restringido que ellos llaman codificación cuasi-aritmética binaria. Afirman que la diferencia entre las versiones reales y enteras es insignificante, prueban que la pérdida de compresión para su método cuasi-aritmético se puede hacer arbitrariamente pequeña y limitan la pérdida de compresión incurrida por una de sus aproximaciones en menos del 0.06%. Ver: Howard, Paul G .; Vitter, Jeffrey S. (1994), "Codificación aritmética para la compresión de datos" (PDF) , Proceedings of the IEEE , 82 (6): 857–865, doi : 10.1109 / 5.286189 , hdl : 1808/7229 , archivado desde el original (PDF) el 18 de octubre de 2013 , consultado el 17 de octubre de 2013.

Referencias

MacKay, David JC (septiembre de 2003). "Capítulo 6: Códigos de flujo" . Teoría de la información, inferencia y algoritmos de aprendizaje . Prensa de la Universidad de Cambridge . ISBN 0-521-64298-1. Archivado desde el original (PDF / PostScript / DjVu / LaTeX ) el 22 de diciembre de 2007 . Consultado el 30 de diciembre de 2007 .
Presione, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 22.6. Codificación aritmética" . Recetas numéricas: el arte de la informática científica (3ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.
Rissanen, Jorma (mayo de 1976). "Codificación aritmética y desigualdad generalizada de Kraft" . IBM Journal of Research and Development . 20 (3): 198-203. doi : 10.1147 / rd.203.0198 . Consultado el 21 de septiembre de 2007 .
Rissanen, JJ; Langdon GG, Jr (marzo de 1979). "Codificación aritmética" (PDF) . IBM Journal of Research and Development . 23 (2): 149-162. doi : 10.1147 / rd.232.0149 . Archivado desde el original (PDF) el 28 de septiembre de 2007 . Consultado el 22 de septiembre de 2007 .
Witten, Ian H .; Neal, Radford M .; Cleary, John G. (junio de 1987). "Codificación aritmética para la compresión de datos" (PDF) . Comunicaciones de la ACM . 30 (6): 520–540. doi : 10.1145 / 214762.214771 . Archivado (PDF) desde el original el 28 de septiembre de 2007 . Consultado el 21 de septiembre de 2007 .

Rodionov Anatoly, Volkov Sergey (2010) "codificación aritmética p-ádica" Matemáticas contemporáneas Volumen 508, 2010 Matemáticas contemporáneas
Rodionov Anatoly, Volkov Sergey (2007) "codificación aritmética p-adic", https://arxiv.org/abs//0704.0834v1

enlaces externos

Este artículo incorpora material de dominio público del documento NIST : Black, Paul E. "codificación aritmética" . Diccionario de algoritmos y estructuras de datos .
Publicación en grupos de noticias con un breve ejemplo elaborado de codificación aritmética (solo enteros).
Artículo de PlanetMath sobre codificación aritmética
Anatomía del codificador de rango El artículo explica tanto la codificación de rango como la aritmética. También tiene ejemplos de código para 3 codificadores aritméticos diferentes junto con una comparación de rendimiento.
Introducción a la codificación aritmética . 60 páginas.
Eric Bodden, Malte Clasen y Joachim Kneis: Codificación aritmética revelada . Informe técnico 2007-5, Grupo de investigación Sable, Universidad McGill.
Codificación aritmética + Modelado estadístico = Compresión de datos por Mark Nelson.
Compresión de datos con codificación aritmética por Mark Nelson (2014)
Implementación rápida de codificación de rango y rANS por James K. Bonfield

[LiDrew2014-1] Ze-Nian Li; Mark S. Drew; Jiangchuan Liu (9 de abril de 2014). Fundamentos de Multimedia . Springer Science & Business Media. ISBN 978-3-319-05290-8.

[PCS2015-2] J. Duda, K. Tahboub, NJ Gadil, EJ Delp, El uso de sistemas numéricos asimétricos como un reemplazo preciso para la codificación de Huffman , Simposio de codificación de imágenes, 2015.

[3] Richard Clark Pasco, "Algoritmos de codificación de origen para la compresión rápida de datos", Ph.D. disertación, Stanford Univ., mayo de 1976.

[4] [1] ¿Qué es JPEG? Comp.compression Preguntas frecuentes (parte 1/3)

[5] "Recomendación T.81 (1992) Corrigendum 1 (04/01)" . Recomendación T.81 (1992) . Unión Internacional de Telecomunicaciones. 9 de noviembre de 2004 . Consultado el 3 de febrero de 2011 .

[6] Estándar de compresión de datos de imagen fija JPEG , WB Pennebaker y JL Mitchell , Kluwer Academic Press, 1992. ISBN 0-442-01272-1

[t81-7] "T.81 - COMPRESIÓN DIGITAL Y CODIFICACIÓN DE IMÁGENES FIJAS EN TONO CONTINUO - REQUISITOS Y DIRECTRICES" (PDF) . CCITT . Septiembre de 1992 . Consultado el 12 de julio de 2019 .

[8] [2] Comp.compression Preguntas frecuentes (parte 1/3)

[9] [3] Lanzamiento del códec de vídeo 1.0 de Dirac

[10] Por ejemplo, Howard y Vitter (1994) discuten versiones de codificación aritmética basadas en rangos de números reales, aproximaciones enteras a esos rangos y un tipo de aproximación aún más restringido que ellos llaman codificación cuasi-aritmética binaria. Afirman que la diferencia entre las versiones reales y enteras es insignificante, prueban que la pérdida de compresión para su método cuasi-aritmético se puede hacer arbitrariamente pequeña y limitan la pérdida de compresión incurrida por una de sus aproximaciones en menos del 0.06%. Ver: Howard, Paul G .; Vitter, Jeffrey S. (1994), "Codificación aritmética para la compresión de datos" (PDF) , Proceedings of the IEEE , 82 (6): 857–865, doi : 10.1109 / 5.286189 , hdl : 1808/7229 , archivado desde el original (PDF) el 18 de octubre de 2013 , consultado el 17 de octubre de 2013.

Languages

In other projects