La codificación de rango es un método de codificación de entropía definido por G. Nigel N. Martin en un artículo de 1979, [1] que redescubrió efectivamente el código aritmético FIFO introducido por primera vez por Richard Clark Pasco en 1976. [2] Dado un flujo de símbolos y sus probabilidades , un codificador de rango produce un flujo de bits de uso eficiente del espacio para representar estos símbolos y, dados el flujo y las probabilidades, un decodificador de rango invierte el proceso.
La codificación de rango es muy similar a la codificación aritmética , excepto que la codificación se realiza con dígitos en cualquier base, en lugar de con bits, por lo que es más rápida cuando se utilizan bases más grandes (por ejemplo, un byte ) a un costo reducido en eficiencia de compresión. [3] Después de la expiración de la primera patente de codificación aritmética (1978), [4] la codificación de rango parecía estar claramente libre de gravámenes de patente. Esto impulsó particularmente el interés en la técnica en la comunidad de código abierto . Desde entonces, las patentes de varias técnicas de codificación aritmética conocidas también han expirado.
Cómo funciona la codificación de rango
La codificación de rango codifica conceptualmente todos los símbolos del mensaje en un número, a diferencia de la codificación de Huffman, que asigna a cada símbolo un patrón de bits y concatena todos los patrones de bits juntos. Por lo tanto, la codificación de rango puede lograr mayores relaciones de compresión que el límite inferior de un bit por símbolo en la codificación de Huffman y no sufre las ineficiencias que Huffman tiene cuando se trata de probabilidades que no son potencias exactas de dos .
El concepto central detrás de la codificación de rango es el siguiente: dado un rango de números enteros lo suficientemente grande y una estimación de probabilidad para los símbolos, el rango inicial se puede dividir fácilmente en subrangos cuyos tamaños son proporcionales a la probabilidad del símbolo que representan. Cada símbolo del mensaje se puede codificar a su vez, reduciendo el rango actual a ese subrango que corresponde al siguiente símbolo que se codificará. El decodificador debe tener la misma estimación de probabilidad que el codificador utilizado, que puede ser enviado por adelantado, derivado de datos ya transferidos o ser parte del compresor y descompresor.
Cuando se han codificado todos los símbolos, la mera identificación del subrango es suficiente para comunicar el mensaje completo (suponiendo, por supuesto, que el decodificador sea notificado de alguna manera cuando haya extraído el mensaje completo). En realidad, un solo entero es suficiente para identificar el subrango, y puede que ni siquiera sea necesario transmitir el entero completo; si hay una secuencia de dígitos tal que cada entero que comienza con ese prefijo cae dentro del subrango, entonces el prefijo solo es todo lo que se necesita para identificar el subrango y así transmitir el mensaje.
Ejemplo
Supongamos que queremos codificar el mensaje "AABA
A: [0, 60000)B: [60000, 80000): [80000, 100000)
Dado que nuestro primer símbolo es una A, reduce nuestro rango inicial a [0, 60000). La segunda opción de símbolo nos deja con tres subrangos de este rango. Les mostramos siguiendo la 'A' ya codificada:
AA: [0, 36000)AB: [36000, 48000)A: [48000, 60000)
Con dos símbolos codificados, nuestro rango ahora es [0, 36000) y nuestro tercer símbolo conduce a las siguientes opciones:
AAA: [0, 21600)AAB: [21600, 28800)AA: [28800, 36000)
Esta vez es la segunda de nuestras tres opciones la que representa el mensaje que queremos codificar, y nuestro rango se convierte en [21600, 28800). Puede parecer más difícil determinar nuestros subrangos en este caso, pero en realidad no lo es: podemos simplemente restar el límite inferior del límite superior para determinar que hay 7200 números en nuestro rango; que los primeros 4320 de ellos representan 0,60 del total, los 1440 siguientes representan el 0,20 siguientes y los 1440 restantes representan los 0,20 restantes del total. Sumando el límite inferior nos da nuestros rangos:
AABA: [21600, 25920)AABB: [25920, 27360)AAB: [27360, 28800)
Finalmente, con nuestro rango reducido a [21600, 25920), solo tenemos un símbolo más para codificar. Usando la misma técnica que antes para dividir el rango entre el límite superior e inferior, encontramos que los tres subrangos son:
AABAA: [21600, 24192)AABAB: [24192, 25056)AABA: [25056, 25920)
Y dado que
El problema central puede parecer ser seleccionar un rango inicial lo suficientemente grande como para que no importa cuántos símbolos tengamos que codificar, siempre tendremos un rango actual lo suficientemente grande como para dividirlo en subrangos distintos de cero. En la práctica, sin embargo, esto no es un problema, porque en lugar de comenzar con un rango muy grande y reducirlo gradualmente, el codificador trabaja con un rango de números más pequeño en un momento dado. Después de que se hayan codificado algunos dígitos, los dígitos más a la izquierda no cambiarán. En el ejemplo, después de codificar solo tres símbolos, ya sabíamos que nuestro resultado final comenzaría con "2". Se desplazan más dígitos a la derecha a medida que se envían los dígitos de la izquierda. Esto se ilustra en el siguiente código:
int bajo = 0 ; int rango = 100000 ;void Run () { Codificar ( 0 , 6 , 10 ); // Una codificación ( 0 , 6 , 10 ); // Una codificación ( 6 , 2 , 10 ); // Codificación B ( 0 , 6 , 10 ); // Una codificación ( 8 , 2 , 10 ); // // emitir dígitos finales - ver más abajo while ( rango < 10000 ) EmitDigit ();bajo + = 10000 ; EmitDigit (); }void EmitDigit () { Console . Escribir ( bajo / 10000 ); bajo = ( % bajo 10000 ) * 10 ; rango * = 10 ; } void Encode ( int start , int size , int total ) { // ajusta el rango basado en el rango del intervalo del símbolo / = total ; bajo + = inicio * rango ; rango * = tamaño ;// verifica si el dígito más a la izquierda es el mismo en todo el rango while ( bajo / 10000 == ( rango + bajo ) / 10000 ) EmitDigit (); // reajuste el rango - vea la razón de esto a continuación if ( rango < 1000 ) { EmitDigit (); EmitDigit (); rango = 100000 - bajo ; } }
Para terminar, es posible que necesitemos emitir algunos dígitos adicionales. El dígito superior de low
probablemente sea demasiado pequeño, por lo que debemos incrementarlo, pero debemos asegurarnos de no incrementarlo más allá low+range
. Entonces, primero debemos asegurarnos de que range
sea lo suficientemente grande.
// Emite los dígitos finales while ( rango < 10000 ) EmitDigit ();bajo + = 10000 ; EmitDigit ();
Un problema que puede ocurrir con la Encode
función anterior es que range
puede llegar a ser muy pequeñas, pero low
y low+range
todavía tienen diferentes primeros dígitos. Esto podría dar como resultado que el intervalo tenga una precisión insuficiente para distinguir entre todos los símbolos del alfabeto. Cuando esto sucede, debemos modificar un poco, generar los primeros dos dígitos aunque estemos desfasados en uno y reajustar el rango para darnos la mayor cantidad de espacio posible. El decodificador seguirá los mismos pasos, por lo que sabrá cuándo debe hacer esto para mantenerse sincronizado.
// esto va justo antes del final de Encode () arriba if ( rango < 1000 ) { EmitDigit (); EmitDigit (); rango = 100000 - bajo ; }
En este ejemplo se usó Base 10, pero una implementación real solo usaría binario, con el rango completo del tipo de datos enteros nativos. En lugar de 10000
y 1000
probablemente usaría constantes hexadecimales como 0x1000000
y 0x10000
. En lugar de emitir un dígito a la vez, emitiría un byte a la vez y utilizaría una operación de desplazamiento de bytes en lugar de multiplicar por 10.
La decodificación utiliza exactamente el mismo algoritmo con la adición de realizar un seguimiento del code
valor actual que consta de los dígitos leídos del compresor. En lugar de emitir el dígito superior low
, simplemente deséchelo, pero también desplaza el dígito superior de code
y cambia un nuevo dígito leído desde el compresor. Utilice a AppendDigit
continuación en lugar de EmitDigit
.
código int = 0 ; int bajo = 0 ; int rango = 1 ;void InitializeDecoder () { AppendDigit (); // con este código de ejemplo, solo 1 de estos es realmente necesario AppendDigit (); AppendDigit (); AppendDigit (); AppendDigit (); }void AppendDigit () { código = ( código % 10000 ) * 10 + ReadNextDigit (); bajo = ( % bajo 10000 ) * 10 ; rango * = 10 ; } void Decode ( int start , int size , int total ) // Decode es igual que Encode con EmitDigit reemplazado por AppendDigit { // ajusta el rango basado en el intervalo de símbolo range / = total ; bajo + = inicio * rango ; rango * = tamaño ;// verifica si el dígito más a la izquierda es el mismo en todo el rango while ( bajo / 10000 == ( rango + bajo ) / 10000 ) AppendDigit (); // reajuste el rango - vea la razón de esto a continuación if ( rango < 1000 ) { AppendDigit (); AppendDigit (); rango = 100000 - bajo ; } }
Para determinar qué intervalos de probabilidad aplicar, el decodificador necesita mirar el valor actual code
dentro del intervalo (rango bajo, bajo +) y decidir qué símbolo representa.
void Run () { int inicio = 0 ; int tamaño ; int total = 10 ; InitializeDecoder (); // necesita obtener rango / total> 0 while ( inicio < 8 ) // detener cuando recibe EOM { int v = GetValue ( total ); // ¿El código está en qué rango de símbolos? switch ( v ) // convertir valor en símbolo { caso 0 : caso 1 : caso 2 : caso 3 : caso 4 : caso 5 : inicio = 0 ; tamaño = 6 ; Consola . Escribe ( "A" ); romper ; caso 6 : caso 7 : inicio = 6 ; tamaño = 2 ; Consola . Escribir ( "B" ); romper ; predeterminado : inicio = 8 ; tamaño = 2 ; Consola . WriteLine ( "" ); } Decodificar ( inicio , tamaño , total ); } }int GetValue ( int total ) { return ( código - bajo ) / ( rango / total ); }
Para el ejemplo de AABA
Relación con la codificación aritmética
La codificación aritmética es la misma que la codificación de rango, pero los enteros se toman como numeradores de fracciones . Estas fracciones tienen un denominador común implícito, de modo que todas las fracciones caen en el rango [0,1). En consecuencia, el código aritmético resultante se interpreta como que comienza con un "0" implícito. Como estas son solo diferentes interpretaciones de los mismos métodos de codificación, y como los códigos aritméticos y de rango resultantes 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 solo dos formas ligeramente diferentes de entender lo mismo.
En la práctica, sin embargo, los denominados codificadores de rango tienden a implementarse más o menos como se describe en el artículo de Martin, [1] mientras que los codificadores aritméticos en general no suelen llamarse codificadores de rango. Una característica que se observa a menudo de estos codificadores de rango es la tendencia a realizar la renormalización un byte a la vez, en lugar de un bit a la vez (como suele ser el caso). En otras palabras, los codificadores de rango tienden a usar bytes como dígitos de codificación, en lugar de bits. Si bien esto reduce la cantidad de compresión que se puede lograr en una cantidad muy pequeña, es más rápido que cuando se realiza la renormalización para cada bit.
Ver también
Referencias
- ^ a b G. Nigel N. Martin, Codificación de rango: un algoritmo para eliminar la redundancia de un mensaje digitalizado , Conferencia de grabación de video y datos, Southampton , Reino Unido, 24 al 27 de julio de 1979.
- ^ "Algoritmos de codificación de origen para la compresión rápida de datos" Richard Clark Pasco, Stanford, CA 1976
- ^ " Sobre la cabeza de los codificadores de rango ", Timothy B. Terriberry, Nota técnica 2008
- ^ Patente de EE . UU . 4,122,440 - (IBM) presentada el 4 de marzo de 1977, otorgada el 24 de octubre de 1978 (ahora vencida)