Codificación de rango - Range coding
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, que redescubrió efectivamente el código aritmético FIFO introducido por primera vez por Richard Clark Pasco en 1976. 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, 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, 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. 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 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 tiene 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 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 <EOM>", donde <EOM> es el símbolo de fin de mensaje. Para este ejemplo, se asume que el decodificador sabe que pretendemos codificar exactamente cinco símbolos en el sistema numérico de base 10 (permitiendo 10 5 combinaciones diferentes de símbolos con el rango [0, 100000)) usando la distribución de probabilidad {A:. 60; B: .20; <EOM>: .20}. El codificador divide 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. Les mostramos siguiendo la 'A' ya codificada:
AA: [ 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 sub-rangos 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 el 0,20 restantes del total. Sumando el límite inferior nos da nuestros rangos:
AABA: [21600, 25920) AABB: [25920, 27360) AAB<EOM>: [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<EOM>: [25056, 25920)
Y dado que <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" caen dentro de nuestro rango final, es uno de los prefijos de tres dígitos que podríamos transmitir y que transmitiría sin ambigüedades nuestro mensaje original. (El hecho de que en realidad haya ocho prefijos de este tipo en total implica que todavía tenemos ineficiencias. Han sido introducidas por nuestro uso de base 10 en lugar de base 2 ).
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 low = 0;
int range = 100000;
void Run()
{
Encode(0, 6, 10); // A
Encode(0, 6, 10); // A
Encode(6, 2, 10); // B
Encode(0, 6, 10); // A
Encode(8, 2, 10); // <EOM>
// emit final digits - see below
while (range < 10000)
EmitDigit();
low += 10000;
EmitDigit();
}
void EmitDigit()
{
Console.Write(low / 10000);
low = (low % 10000) * 10;
range *= 10;
}
void Encode(int start, int size, int total)
{
// adjust the range based on the symbol interval
range /= total;
low += start * range;
range *= size;
// check if left-most digit is same throughout range
while (low / 10000 == (low + range) / 10000)
EmitDigit();
// readjust range - see reason for this below
if (range < 1000)
{
EmitDigit();
EmitDigit();
range = 100000 - low;
}
}
Para terminar, 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á low+range. Entonces, primero debemos asegurarnos de que rangesea lo suficientemente grande.
// emit final digits
while (range < 10000)
EmitDigit();
low += 10000;
EmitDigit();
Un problema que puede ocurrir con la Encodefunción anterior es que rangepuede llegar a ser muy pequeñas, pero lowy low+rangetodaví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 el primer par de 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.
// this goes just before the end of Encode() above
if (range < 1000)
{
EmitDigit();
EmitDigit();
range = 100000 - low;
}
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 10000y 1000probablemente usarí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 la adición de realizar un seguimiento del codevalor 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 codey cambia un nuevo dígito leído desde el compresor. Utilice a AppendDigitcontinuación en lugar de EmitDigit.
int code = 0;
int low = 0;
int range = 1;
void InitializeDecoder()
{
AppendDigit(); // with this example code, only 1 of these is actually needed
AppendDigit();
AppendDigit();
AppendDigit();
AppendDigit();
}
void AppendDigit()
{
code = (code % 10000) * 10 + ReadNextDigit();
low = (low % 10000) * 10;
range *= 10;
}
void Decode(int start, int size, int total) // Decode is same as Encode with EmitDigit replaced by AppendDigit
{
// adjust the range based on the symbol interval
range /= total;
low += start * range;
range *= size;
// check if left-most digit is same throughout range
while (low / 10000 == (low + range) / 10000)
AppendDigit();
// readjust range - see reason for this below
if (range < 1000)
{
AppendDigit();
AppendDigit();
range = 100000 - low;
}
}
Para determinar qué intervalos de probabilidad aplicar, el decodificador necesita mirar el valor actual codedentro del intervalo (rango bajo, bajo +) y decidir qué símbolo representa.
void Run()
{
int start = 0;
int size;
int total = 10;
InitializeDecoder(); // need to get range/total >0
while (start < 8) // stop when receive EOM
{
int v = GetValue(total); // code is in what symbol range?
switch (v) // convert value to symbol
{
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 (code - low) / (range / total);
}
Para el ejemplo de AABA <EOM> anterior, esto devolvería un valor en el rango de 0 a 9. Los valores de 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 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 comenzando 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.
Sin embargo, en la práctica, los denominados codificadores de rango tienden a implementarse de manera muy similar a 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 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
- Codificación aritmética
- Sistemas numéricos asimétricos
- Compresión de datos
- Codificación de entropía
- Codificación Huffman
- Formato de electrofisiología multiescala
- Codificación Shannon-Fano
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)