Rango de codificación

Rango de Codificación es un método de compresión de datos definido por G.N.N. Martín en su "paper" de 1979 "Range encoding: an algorithm for removing redundancy from a digitized message".^[1] El rango de codificación es matemáticamente equivalente a la codificación aritmética. Estas implementaciones son conocidas por ser libre de patentes relacionadas con la codificación aritmética, sobre la base del "paper" de G.N.N. Martín. Esta clara falta de gravamen de patentes ha impulsado el interés en el rango de codificación, en particular en la comunidad de código abierto.

Funcionamiento

El rango de codificación codifica todos los símbolos del mensaje en el número uno, a diferencia de la codificación Huffman que asigna a cada símbolo un patrón de bits y concatena todos los patrones de bits juntos. Así el rango de codificación pueden alcanzar ratios de compresión mayor que el de bits por símbolo de límite superior de la codificación Huffman y no sufrir las ineficiencias de la codificación Huffman cuando se trata de probabilidades, que no son potencias exactas de dos.

La idea central detrás de codificación serie es la siguiente: dado un gran rango suficiente de números enteros, y una estimación de probabilidad de los símbolos, el rango inicial puede fácilmente ser dividido en sub-rangos cuyos tamaños son proporcionales a la probabilidad del símbolo que representan. Cada símbolo del mensaje puede ser codificado a su vez, mediante la reducción del rango actual hasta que se acaba en el sub-rango que corresponde al símbolo que está junto a ser codificado. El decodificador debe tener la misma probabilidad de estimación del codificador utilizado, que puede ser enviado con anticipación, derivada de los datos ya transferidos o ser parte del compresor y descompresor.

Cuando todos los símbolos han sido codificados, se limita a la identificación del sub-rango, si es suficiente para comunicar el mensaje completo. Un solo número entero es realmente suficiente para identificar al sub-rango de distribución, y puede incluso no ser necesarios para transmitir todo el entero, si hay una secuencia de dígitos tal que cada principio entero con prefijo cae dentro del sub-rango de distribución, entonces el prefijo solo es todo lo que se necesita para identificar los sub-rangos de distribución y así transmitir el mensaje.

Relación con la Codificación aritmética

La codificación aritmética es la misma que la codificación rango, pero con los números enteros tomado como los numeradores de las fracciones. Estas fracciones tienen un implícito, denominador común, de manera que todas las fracciones caídas en el intervalo [0,1). En consecuencia, el código de la aritmética resultante se interpreta como el principio con un implícito "0". Como se trata de interpretaciones solo diferentes métodos de codificación de la misma, y como la media aritmética resultante y los códigos de serie son idénticos, cada codificador aritmético es su codificador de rango correspondiente, y viceversa. En otras palabras, la codificación aritmética y la codificación de rango son sólo dos formas ligeramente diferentes de entender la misma cosa.

En la práctica, sin embargo, los llamados codificadores de rango tienden a ser aplicado más o menos como se describe en el "paper" de G.N.N. Martín, mientras que la codificación aritmética en general no tienden a ser llamados codificadores de rango. Un aspecto señalado con frecuencia es la tendencia a realizar renormalización un byte a la vez, en lugar de un bit a la vez. En otras palabras, los codificadores de rango tienden a utilizar la bytes como codificación de dígitos, en lugar de bits. Si bien esto reduce la cantidad de compresión que puede ser alcanzado por un valor muy pequeño, es más rápido que en el desempeño de renormalización para cada bit.

Referencias

↑ Range Encoder

Enlaces externos

Datos: Q818947

[compressconsult-1] Range Encoder

[1]