Saltar a contenido

Range Encoding

Descripción

La codificación por rangos (Range Encoding) es un algoritmo de codificación en el que se asignan códigos a los símbolos dependiendo de la probabilidad acumulada de aparición. Este algoritmo funciona de manera similar a Arithmetic encoding, con la diferencia que Arithmetic encoding considera siempre el intervalo [0,1), mientras que Range encoding considera intervalos más amplios, con el objetivo de representar las secuencias mediante un número entero.

Funcionamiento

La idea detrás de la codificación es la siguiente: Dado un rango de números, y una estimación inicial de la probabilidad de cada símbolo, el rango se puede subdividir en subrangos, de tal manera que el largo de estos subrangos esté en proporción con la probabilidad del símbolo que representan. Para codificar un texto, se va restringiendo el rango, de acuerdo a los subrangos de cada símbolo, en orden de aparición.

La idea de dividir los rangos en subrangos proporcionales a la probabilidad de aparición de los símbolos es para que los símbolos más probables en aparecer tengan un rango más amplio para subdividir que los demás, aprovechando de mejor manera el intervalo.

Ejemplo de codificación

A continuación daremos un ejemplo para ilustrar de mejor manera la idea. Vamos a considerar la secuencia BAD, con la distribución de probabilidad {B=0.6, A=0.2, D=0.2}. Además, consideraremos el rango inicial como [0,1000).

Con esto, vemos los intervalos asociados a cada símbolo en el rango original:

Símbolo Rango
B [0,600)
A [600,800)
D [800, 1000)

Dado que el primer símbolo es B, restringimos el rango a [0,600). La idea ahora es considerar un intervalo para una secuencia de la forma BX, siendo X otro símbolo del alfabeto. Para ello, restringimos el rango original al rango de B, y recalculamos los intervalos de acuerdo a la probabilidad de cada símbolo:

Símbolo Rango
BB [0,360)
BA [360,480)
BD [480, 600)

Así, la secuencia BA correspondería al intervalo [360,480). Por tanto, continuaremos trabajando sobre este intervalo. Ahora, recalculamos los intervalos de cada símbolo para el intervalo de BA:

Símbolo Rango
BAB [360,432)
BAA [432,456)
BAD [456, 480)

De esta manera, la secuencia BAD estaría representada por cualquier valor en el intervalo [456,480).

Ejemplo de decodificación

Para decodificar la secuencia, necesitamos el valor obtenido, junto a la distribución de probabilidad inicial. A modo de ejemplo, tomaremos la misma función de distribución considerada en el ejemplo anterior, {B=0.6, A=0.2, D=0.2}, y el valor 400. Considerando el intervalo original [0,1000), tenemos que los subrangos son:

Símbolo Rango
B [0,600)
A [600,800)
D [800, 1000)

Por tanto, el número 400 corresponde a una secuencia que comienza con B. Luego, restringimos el intervalo sobre el que trabajamos al intervalo [0,600). Recalculando los intervalos, vemos que:

Símbolo Rango
BB [0,360)
BA [360,480)
BD [480, 600)

Aquí podemos observar que 400 cae en el intervalo correspondiente a BA, por lo que restringimos nuevamente el intervalo, y recalculamos los subintervalos correspondientes:

Símbolo Rango
BAB [360,432)
BAA [432,456)
BAD [456, 480)

En este punto observamos que 400 está en el intervalo de BAB, por lo que, si sabemos que la secuencia consta de 3 elementos, la secuencia original sería BAB. Para un caso general, no se conoce el largo de la secuencia antes de decodificar, por lo que, para detener el proceso de decodificación, a las secuencias se les asigna un símbolo que indica el final de la secuencia. Este símbolo también tendrá un rango asociado, de manera que al decodificar, si se llega al intervalo correspondiente a este símbolo, se sabe que se debe detener el proceso de codificación.

Implementación

A continuación daremos un ejemplo ilustrativo de un código en C++ para esta codificación, considerando el rango [0,1): 

#include  <iostream>
#include  <vector>
#include  <string>
#include  <cmath>

class  RangeEncoder  {
    public:
        RangeEncoder(std::vector<double>&  probabilities)  :  probabilities_(probabilities){

        // Inicializar los intervalos basados en las probabilidades acumulativas
        cumulative_probabilities_.resize(probabilities.size());
        cumulative_probabilities_[0]  =  probabilities_[0];
        for  (size_t  i  =  1;  i  <  probabilities.size();  ++i)  {
            cumulative_probabilities_[i]  =  cumulative_probabilities_[i  -  1]  +          probabilities_[i];
        }
    } 
    // Codificar una secuencia de símbolos
    std::pair<double,  double>  encode(const  std::string&  input)  {
        double  low  =  0.0;
        double  range  =  1.0;
        for  (char  c  :  input)  {
            size_t  symbol_index  =  static_cast<size_t>(c  -  'A');
            double  symbol_low  =  cumulative_probabilities_[symbol_index]  -  probabilities_[symbol_index];
            low  =  low  +  range  *  symbol_low;
            range  =  range  *  (probabilities_[symbol_index]);
        }
        return  {  low,  low  +  range  };
    }
    private:
    std::vector<double>  probabilities_;
    std::vector<double>  cumulative_probabilities_;
};

class  RangeDecoder  {
    public:
    RangeDecoder(std::vector<double>&  probabilities)  :  probabilities_(probabilities)  {
    // Inicializar los intervalos basados en las probabilidades acumulativas
        cumulative_probabilities_.resize(probabilities.size());
        cumulative_probabilities_[0]  =  probabilities_[0];
        for  (size_t  i  =  1;  i  <  probabilities.size();  ++i)  {
            cumulative_probabilities_[i]  =  cumulative_probabilities_[i  -  1]  +  probabilities_[i];
        }
    }
    // Decodificar un valor en una secuencia de símbolos
    std::string  decode(double  value,  size_t  sequence_length)  {
        std::string  decoded_sequence;
        for  (size_t  i  =  0;  i  <  sequence_length;  ++i)  {
            size_t  j;
            for  (j  =  0;  j  <  probabilities_.size();  ++j)  {
                if  (value  <  cumulative_probabilities_[j])  {
                    decoded_sequence  +=  static_cast<char>('A'  +  j);
                    value  =  (value  -  cumulative_probabilities_[j-1])  /  (cumulative_probabilities_[j]  -  cumulative_probabilities_[j-1]);
                    break;
                }
            }
        // Si el valor está dentro del rango de la última probabilidad acumulativa
            if  (j  ==  probabilities_.size())  {
                decoded_sequence  +=  static_cast<char>('A'  +  j);
                value  =  (value  -  cumulative_probabilities_[j-1])  /  (1.0  -  cumulative_probabilities_[j-1]);
            }
        }
        return  decoded_sequence;
    }
    private:
        std::vector<double>  probabilities_;
        std::vector<double>  cumulative_probabilities_;
};
int  main()  {
    // Probabilidades de los símbolos A, B, C, D
    std::vector<double>  probabilities  =  {0.4,  0.3,  0.2,  0.1};
    // Crear un codificador
    RangeEncoder  encoder(probabilities);
    // Secuencia a codificar
    std::string  input_sequence  =  "DAD";
    // Codificar la secuencia y obtener el rango asociado
    auto  encoded_range  =  encoder.encode(input_sequence);
    std::cout  <<  "Encoded range: ["  <<  encoded_range.first  <<  ", "  <<  encoded_range.second  <<  ")\n";
    // Crear un decodificador
    RangeDecoder  decoder(probabilities);
    // Decodificar el valor
    double  decoded_value  =  (encoded_range.first  +  encoded_range.second)  /  2.0;
    std::string  decoded_sequence  =  decoder.decode(decoded_value,  input_sequence.length());
    std::cout  <<  "Decoded sequence: "  <<  decoded_sequence  <<  std::endl;
    return  0;
}

Para ver implementaciones más avanzadas y eficientes, invitamos a revisar las implementaciones presentadas en las referencias.

Información adicional

Como se ha visto en las secciones anteriores, la codificación depende del rango elegido. Sin embargo, este rango puede no siempre ser adecuado. Esto es, puede darse que al codificar una palabra, los subrangos obtenidos sean demasiado pequeños para subdividirlos de manera adecuada. Una opción mencionada por los autores del algoritmo es modificar los rangos a medida que eso pase, agregando dígitos a conveniencia. Por ejemplo, si el rango [700, 730) es demasiado pequeño, se puede ampliar a [7000,7300) agregando un 0 al final. Evidentemente, esto afecta al código obtenido, y al proceso de codificación, pues se vuelve necesario incluir una manera de indicar que el rango fue ampliado.

Otra consideración a tener en cuenta corresponde a las probabilidades de los símbolos. Anteriormente, explicamos el algoritmo con una función de densidad estática, pero es posible adaptar el algoritmo de tal manera que se trabaje con una densidad dinámica.

Referencias