La codificación de rango (o 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 eficiente en el espacio para representar estos símbolos y, dado 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, y por lo tanto es más rápida cuando se utilizan bases más grandes (por ejemplo, un byte ) a un pequeño costo 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 patentes. Esto impulsó particularmente el interés en la técnica en la comunidad de código abierto . Desde ese momento, las patentes de varias técnicas de codificación aritmética bien conocidas también han expirado.
La codificación de rango codifica conceptualmente todos los símbolos del mensaje en un solo 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. Por lo tanto, la codificación de rango puede lograr mayores índices de compresión que el límite inferior de un bit por símbolo de la codificación de Huffman y no sufre las ineficiencias que sufre Huffman cuando se trabaja con probabilidades que no son una potencia exacta de dos .
El concepto central detrás de la codificación de rango es el siguiente: dado un rango suficientemente grande de números enteros 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 solo ese subrango que corresponde al siguiente símbolo que se va a codificar. El decodificador debe tener la misma estimación de probabilidad que utilizó el codificador, que puede enviarse por adelantado, derivarse de datos ya transferidos o ser parte del compresor y descompresor.
Cuando se han codificado todos los símbolos, basta con identificar el subrango para comunicar el mensaje completo (suponiendo, por supuesto, que el decodificador reciba de algún modo una notificación cuando haya extraído el mensaje completo). En realidad, un solo número entero es suficiente para identificar el subrango, y puede que ni siquiera sea necesario transmitir el número entero completo; si existe una secuencia de dígitos tal que cada número entero que comience con ese prefijo se encuentre dentro del subrango, entonces el prefijo por sí solo es todo lo que se necesita para identificar el subrango y, por lo tanto, transmitir el mensaje.
Supongamos que queremos codificar el mensaje "AABA<EOM>", donde <EOM> es el símbolo de fin de mensaje. Para este ejemplo, se supone que el decodificador sabe que pretendemos codificar exactamente cinco símbolos en el sistema numérico de base 10 (lo que permite 10 5 combinaciones diferentes de símbolos con el rango [0, 100000)) utilizando la distribución de probabilidad {A: .60; B: .20; <EOM>: .20}. El codificador descompone el rango [0, 100000) en tres subrangos:
A: [0, 60000)B: [60000, 80000)<EOM>: [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. Los mostramos a continuación de la 'A' ya codificada:
Automóvil club británico: [0, 36000)AB: [36000, 48000)A<EOM>: [ 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<EOM>: [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: simplemente podemos 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 el 0,60 del total, los siguientes 1440 representan el siguiente 0,20 y los 1440 restantes representan el 0,20 restante del total. Al sumar nuevamente el límite inferior obtenemos nuestros rangos:
AABA: [21600, 25920)ABB: [25920, 27360)AAB<EOM>: [27360, 28800)
Finalmente, con nuestro rango reducido a [21600, 25920), tenemos solo un símbolo más para codificar. Usando la misma técnica que antes para dividir el rango entre el límite inferior y el superior, encontramos que los tres subrangos son:
AABAA: [21600, 24192)AABAB: [24192, 25056)AABA<EOM>: [25056, 25920)
Y como <EOM> es nuestro símbolo final, nuestro rango final es [25056, 25920). Debido a que todos los números enteros de cinco dígitos que comienzan con "251" se encuentran dentro de nuestro rango final, es uno de los prefijos de tres dígitos que podríamos transmitir y que transmitiría de manera inequívoca nuestro mensaje original. (El hecho de que en realidad haya ocho prefijos de este tipo en total implica que aún tenemos ineficiencias. Han sido introducidas por nuestro uso de la base 10 en lugar de la base 2 ).
El problema central puede parecer el de seleccionar un rango inicial lo suficientemente grande como para que, sin importar cuántos símbolos tengamos que codificar, siempre tengamos 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 haya codificado una cierta cantidad de 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 hacia 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 ) ; // A Codificar ( 0 , 6 , 10 ); // A Codificar ( 6 , 2 , 10 ); // B Codificar ( 0 , 6 , 10 ); // A Codificar ( 8 , 2 , 10 ); // <EOM> // emitir dígitos finales - ver más abajo while ( range < 10000 ) EmitDigit (); bajo += 10000 ; EmitDigit (); } void EmitDigit ( ) { Console.Write ( low / 10000 ) ; low = ( low % 10000 ) * 10 ; rango *= 10 ; } void Encode ( int start , int size , int total ) { // ajusta el rango según el intervalo del símbolo rango /= total ; bajo += inicio * rango ; rango *= tamaño ; // verificar si el dígito más a la izquierda es el mismo en todo el rango while ( low / 10000 == ( low + range ) / 10000 ) EmitDigit (); // reajustar el rango - vea el motivo a continuación if ( range < 1000 ) { EmitDigit (); EmitDigit (); range = 100000 - low ; } } Para finalizar, es posible que necesitemos emitir algunos dígitos adicionales. El dígito superior de lowprobablemente sea demasiado pequeño, por lo que debemos incrementarlo, pero debemos asegurarnos de no incrementarlo más allá de low+range. Por lo tanto, primero debemos asegurarnos de rangeque sea lo suficientemente grande.
// emite dígitos finales while ( range < 10000 ) EmitDigit (); bajo += 10000 ; EmitDigit (); Un problema que puede ocurrir con la Encodefunción anterior es que rangepuede llegar a ser muy pequeña pero lowaún así low+rangetener diferentes primeros dígitos. Esto puede provocar que el intervalo no tenga la precisión suficiente para distinguir entre todos los símbolos del alfabeto. Cuando esto sucede, debemos hacer algunos ajustes, generar los primeros dos dígitos aunque nos equivoquemos en uno y reajustar el rango para darnos el mayor margen posible.
Por ejemplo, imaginemos que el flujo de entrada ha llevado al codificador al intervalo abierto a la derecha [59888, 60188), es decir, low = 59888y range = 300. El truco consiste en reducir el intervalo a [59888, 60000) = [ 59 888, 59 999], lo que permite al codificador emitir dos de los dígitos más a la izquierda de low, y reajustar el intervalo a [88800, 99999] = [88800, 100000), es decir, low = 88800y range = 100000 - low.
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 ( range < 1000 ) { EmitDigit (); EmitDigit (); range = 100000 - low ; } En este ejemplo se utilizó la base 10, pero una implementación real solo utilizaría binario, con el rango completo del tipo de datos entero nativo. En lugar de 10000y, 1000probablemente utilizaría constantes hexadecimales como 0x1000000y 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 el añadido de llevar un registro del codevalor actual que consiste en los dígitos leídos del compresor. En lugar de emitir el dígito superior de low, simplemente lo descarta, pero también desplaza el dígito superior de codey desplaza un nuevo dígito leído del compresor. Utilice AppendDigitlo siguiente en lugar de EmitDigit.
int código = 0 ; int bajo = 0 ; int rango = 1 ; void InitializeDecoder () { AppendDigit (); // con este código de ejemplo, solo se necesita 1 de estos 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 según el intervalo del símbolo range /= total ; low += start * range ; range *= size ; // verificar si el dígito más a la izquierda es el mismo en todo el rango while ( low / 10000 == ( low + range ) / 10000 ) AppendDigit (); // reajustar el rango - vea el motivo a continuación if ( range < 1000 ) { AppendDigit (); AppendDigit (); range = 100000 - low ; } } Para determinar qué intervalos de probabilidad aplicar, el decodificador debe observar el valor actual codedentro del intervalo [bajo, bajo+rango) y decidir qué símbolo representa.
void Run () { int start = 0 ; int size ; int total = 10 ; InitializeDecoder (); // se necesita obtener rango/total >0 while ( start < 8 ) // se detiene cuando se recibe EOM { int v = GetValue ( total ); // ¿en qué rango de símbolos está el código? switch ( v ) // convierte el valor en símbolo { case 0 : case 1 : case 2 : case 3 : case 4 : case 5 : start = 0 ; size = 6 ; Console . Write ( "A" ); break ; case 6 : case 7 : start = 6 ; size = 2 ; Console . Write ( "B" ); break ; default : start = 8 ; size = 2 ; Console . WriteLine ( "" ); } Decode ( start , size , total ); } } int GetValue ( int total ) { return ( código - bajo ) / ( rango / total ); } Para el ejemplo AABA<EOM> anterior, esto devolvería un valor en el rango de 0 a 9. Los valores del 0 al 5 representarían A, 6 y 7 representarían B, y 8 y 9 representarían <EOM>.
La codificación aritmética es la misma que la codificación de rango, pero los números 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 si comenzara con un "0" implícito. Como se trata simplemente de interpretaciones diferentes 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 simplemente dos formas ligeramente diferentes de entender lo mismo.
En la práctica, sin embargo, los denominados codificadores de rango tienden a implementarse de forma muy similar a lo descrito en el artículo de Martin [1] , mientras que los codificadores aritméticos, en general, tienden a no llamarse codificadores de rango. Una característica que se suele observar de estos codificadores de rango es la tendencia a realizar la renormalización byte a byte, en lugar de bit a bit (como suele ser el caso). En otras palabras, los codificadores de rango tienden a utilizar 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.