Codificación de rango

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, que efectivamente redescubrió primero el código aritmético FIFO. introducido por Richard Clark Pasco en 1976. 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 bits, por lo que es más rápida cuando se usan bases más grandes (por ejemplo, un byte) a un costo menor en eficiencia de compresión. Después de la expiración de la primera patente de codificación aritmética (1978), 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 entonces, también han expirado las patentes de varias técnicas de codificación aritmética bien conocidas.

Cómo funciona la codificación de rango

Representación gráfica del proceso de codificación. El mensaje que se está codificando aquí es "AABA seleccionaEOM título"

La codificación de rango codifica conceptualmente todos los símbolos del mensaje en un solo número, 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. Por lo tanto, la codificación de rango puede lograr relaciones de compresión mayores que el límite inferior de un bit por símbolo en la codificación de Huffman y no sufre las ineficiencias que sufre Huffman cuando se trata de 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 lo suficientemente grande de enteros y una estimación de probabilidad para los símbolos, el rango inicial se puede dividir fácilmente en sub-rangos cuyos tamaños son proporcionales a la probabilidad del símbolo. ellos representan. Luego, cada símbolo del mensaje se puede codificar a su vez, reduciendo el rango actual a solo ese sub-rango que corresponde al siguiente símbolo a codificar. El decodificador debe tener la misma estimación de probabilidad que el codificador utilizado, que puede enviarse por adelantado, derivarse de datos ya transferidos o ser parte del compresor y el descompresor.

Cuando todos los símbolos han sido codificados, 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 número entero es suficiente para identificar el subrango, y es posible que ni siquiera sea necesario transmitir el número entero completo; si hay una secuencia de dígitos tal que cada número 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, por lo tanto, transmitir el mensaje.

Ejemplo

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 tenemos la intención de codificar exactamente cinco símbolos en el sistema numérico de base 10 (permitiendo 10⁵ combinaciones diferentes de símbolos con el rango [0, 100000)) usando la distribución de probabilidad {A:.60; B:.20; <MOE>:.20}. El codificador divide el rango [0, 100000) en tres subrangos:

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 elección de símbolo nos deja con tres sub-rangos de este rango. Los mostramos siguiendo el 'A' ya codificado:

AA: [ 0, 36000]
AB: [ 36000, 48000]
Asignado: [ 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)
AAsignaciónEOM titulada: [ 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 los siguientes 0,20 y los restantes 1440 representan los restantes 0,20 del total. Agregar nuevamente el límite inferior nos da nuestros rangos:

AABA: [21600, 25920)
AABB: [25920, 27360)
AAB madeEOM titulada: [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 inferior y superior, encontramos que los tres sub-rangos son:

AABAA: [21600, 24192)
AABAB: [24192, 25056]
AABA hizoEOM título: [25056, 25920)

Y desde que <EOM> es nuestro símbolo final, nuestro rango final es [25056, 25920). Porque todos los números enteros de cinco dígitos que comienzan con "251" caen dentro de nuestro rango final, es uno de los prefijos de tres dígitos que podríamos transmitir que transmitiría sin ambigüedades nuestro mensaje original. (El hecho de que en realidad haya ocho de estos prefijos en total implica que todavía tenemos ineficiencias. Han sido introducidos por nuestro uso de la base 10 en lugar de la base 2).

Puede parecer que el problema central es 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 sub-rangos 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 codificar 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 a la derecha a medida que se envían los dígitos a la izquierda. Esto se ilustra en el siguiente código:

int bajo = 0;int rango = 100000;vacío Corre(){}Código()0, 6, 10);/ ACódigo()0, 6, 10);/ ACódigo()6, 2, 10);/ BCódigo()0, 6, 10);/ ACódigo()8, 2, 10);//// emitir dígitos finales - ver abajomientras ()rango . 10000)EmitDigit();bajo += 10000;EmitDigit();}vacío EmitDigit(){}Consola.Escriba()bajo / 10000);bajo = ()bajo % 10000) * 10;rango *= 10;}vacío Código()int Empieza, int tamaño, int total){}// ajustar el rango basado en el intervalo de símbolorango /= total;bajo += Empieza * rango;rango *= tamaño;// comprobar si el dígito más izquierdo es el mismo a lo largo del rangomientras ()bajo / 10000 == ()bajo + rango) / 10000)EmitDigit();// rango de ajuste - ver la razón de esto abajosi ()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á de low+range. Entonces, primero debemos asegurarnos de que range sea lo suficientemente grande.

// emite dígitos finalesmientras ()rango . 10000)EmitDigit();bajo += 10000;EmitDigit();

Un problema que puede ocurrir con la función Encode anterior es que range puede volverse muy pequeño pero low y low+range todavía tienen primeros dígitos diferentes. Esto podría dar como resultado que el intervalo no tenga suficiente precisión para distinguir entre todos los símbolos del alfabeto. Cuando esto suceda, debemos modificar un poco, generar el primer par de dígitos aunque podamos estar equivocados por uno, y reajustar el rango para darnos el mayor 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() arribasi ()rango . 1000){}EmitDigit();EmitDigit();rango = 100000 - bajo;}

En este ejemplo se usó la base 10, pero una implementación real solo usaría binario, con el rango completo del tipo de datos entero nativo. 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 usaría una operación de cambio de byte en lugar de multiplicar por 10.

La decodificación utiliza exactamente el mismo algoritmo con la adición de realizar un seguimiento del valor actual de code que consiste en los dígitos leídos del compresor. En lugar de emitir el dígito superior de low, simplemente lo tira, pero también desplaza el dígito superior de code y cambia un nuevo dígito leído desde el compresor. Utilice AppendDigit a continuación en lugar de EmitDigit.

int código = 0;int bajo = 0;int rango = 1;vacío InicializeDecoder(){} AppendDigit(); // con este código de ejemplo, sólo 1 de estos es realmente necesario AppendDigit(); AppendDigit(); AppendDigit(); AppendDigit();}vacío AppendDigit(){}código = ()código % 10000) * 10 + ReadNextDigit();bajo = ()bajo % 10000) * 10;rango *= 10;}vacío Decodificación()int Empieza, int tamaño, int total) // Decode es igual que Encode con EmitDigit sustituido por AppendDigit{}// ajustar el rango basado en el intervalo de símbolorango /= total;bajo += Empieza * rango;rango *= tamaño;// comprobar si el dígito más izquierdo es el mismo a lo largo del rangomientras ()bajo / 10000 == ()bajo + rango) / 10000)AppendDigit();// rango de ajuste - ver la razón de esto abajosi ()rango . 1000){}AppendDigit();AppendDigit();rango = 100000 - bajo;}}

Para determinar qué intervalos de probabilidad aplicar, el decodificador debe observar el valor actual de code dentro del intervalo [bajo, bajo+rango] y decidir qué símbolo representa.

vacío Corre(){}int Empieza = 0;int tamaño;int total = 10;InicializeDecoder(); // necesidad de obtener rango/totalmientras ()Empieza . 8) // Parar cuando recibe EOM{}int v = GetValue()total); // código está en qué rango de símbolos?interruptor ()v) // convertir valor a símbolo{}Caso 0:Caso 1:Caso 2:Caso 3:Caso 4:Caso 5: Empieza=0; tamaño=6; Consola.Escriba()"A"); descanso;Caso 6:Caso 7: Empieza=6; tamaño=2; Consola.Escriba()"B"); descanso;por defecto: Empieza=8; tamaño=2; Consola.WriteLine()");}Decodificación()Empieza, tamaño, total);}}int GetValue()int total){}retorno ()código - bajo) / ()rango / total);}

Para la AABA<EOM> ejemplo anterior, esto devolvería un valor en el rango de 0 a 9. Los valores 0 a 5 representarían A, 6 y 7 representarían B, y 8 y 9 representarían <EOM>.

Relación con la codificación aritmética

La codificación aritmética es lo mismo 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, se interpreta que el código aritmético resultante comienza 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 solo dos formas ligeramente diferentes de entender lo mismo.

Sin embargo, en la práctica, los llamados codificadores de rango tienden a implementarse más o menos como se describe en el artículo de Martin, mientras que los codificadores aritméticos en general tienden a no llamarse codificadores de rango. Una característica a menudo observada de tales 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 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.