Codificación y decodificación aritmética con MATLAB

La codificación aritmética es un tipo de codificación de entropía utilizada en la compresión de datos sin pérdidas. Normalmente, una string de caracteres, por ejemplo, las palabras «hey» se representa utilizando un número fijo de bits por carácter.

En el caso más directo, la probabilidad de que ocurra cada símbolo es equivalente. Por ejemplo, piense en un conjunto de tres símbolos, A, B y C, cada uno con la misma probabilidad de ocurrir. La codificación de bloques directa requeriría 2 bits para cada símbolo, lo cual es ineficiente ya que rara vez se utiliza una de las variedades de bits. En otras palabras, A = 00, B = 01 y C = 10, sin embargo, 11 no se usa. Un arreglo cada vez más productivo es hablar de una sucesión de estos tres símbolos como un número racional en base 3 donde cada dígito habla de un símbolo. Por ejemplo, el arreglo “ABBCAB” podría convertirse en 0.011201. En la codificación aritmética como incentivo en el tramo [0, 1). El siguiente paso es codificar este número ternario utilizando un número pareado de guía fija de suficiente precisión para recuperarlo, por ejemplo, 0. 00101100102: esto es solo 10 bits. Esto se puede lograr para arreglos largos debido al hecho de que hay cálculos establecidos productivos para cambiar la base de números subjetivamente exactos.

Cuando todo está dicho y hecho, los codificadores aritméticos pueden ofrecer una salida ideal cercana para algún arreglo aleatorio de símbolos y probabilidades (el valor ideal es – log2P bits para cada símbolo de probabilidad P). Los algoritmos de compresión que utilizan codificación aritmética deciden una estructura de los datos, fundamentalmente una expectativa de qué ejemplos se encontrarán en los símbolos del mensaje. Cuanto más precisa sea esta predicción, más cerca del ideal será el resultado.

Cuando todo está dicho y hecho, cada progresión del procedimiento de codificación, además de la última absoluta, es el equivalente; el codificador tiene fundamentalmente sólo tres bits de información a considerar: El siguiente símbolo que debe ser codificado. El lapso actual (al comienzo del procedimiento de codificación, el tramo se establece en [0,1], pero eso cambiará) Las probabilidades que el modelo permite a cada uno de los diferentes símbolos que son concebibles en esta etapa (como se indica los modelos anteriores, de mayor solicitud o versátiles implican que estas probabilidades no son realmente equivalentes en cada progresión). en la configuración actual. Cualquier tramo relacionado con el símbolo real que está a punto de ser codificado se convierte en el tramo utilizado en la etapa siguiente. En el momento en que se ha codificado la suma total de los símbolos, el siguiente tramo reconoce sin ambigüedades la disposición de los símbolos que lo entregó. Cualquiera que tenga un tramo final similar y un modelo que se esté utilizando puede rehacer la sucesión de símbolos que probablemente ingresó al codificador para generar ese tramo final. No es importante transmitir el último tramo, en cualquier caso; solo es importante transmitir una división que existe en ese lapso. Específicamente, es importante transmitir suficientes dígitos (en cualquier base) de la parte para que todas las divisiones que comiencen con esos dígitos caigan en el último tramo; esto asegurará que el código subsiguiente sea un código de prefijo.

Codificación 

% input string
str = 'GeeksforGeeks';
fprintf('The entered string is : %s\n', str);
 
% length of the string
len = length(str);
fprintf('The length of the string is : %d\n', len);
 
% get unique characters from the string
u = unique(str);
fprintf('The unique characters are : %s\n', u);
 
% length of the unique characters string
len_unique = length(u);
fprintf('The length of unique character string is : %d\n', len_unique);
 
% General lookup table
 
% get zeros of length of unique characters
z = zeros(1, len_unique);
p = zeros(1, len_unique);
 
for i = 1 : len_unique
 
   % in 'z' variable we will find the
   % occurrence of each characters from 'str' 
   z(i) = length(findstr(str, u(i)));
 
   % in 'p' variable we will get
   % probability of those occurrences
   p(i) = z(i) / len;
end
display(z);
display(p);
 
% in 'cpr' variable we will get the cumulative
% summation of 'p' from '1' till last value of 'p'
cpr = cumsum(p);
 
% in 'newcpr' variable we are taking
% 'cpr' from '0' till last value of 'p'
newcpr = [0 cpr];
 
display(cpr);
display(newcpr);
 
% make table till 'len_unique' size
for i = 1 : len_unique
 
   % in first column we are then
   % placing 'newcpr' values
   interval(i, 1) = newcpr(i);
 
   % in second column we are
   % placing 'cpr' values
   interval(i, 2) = cpr(i);
end
 
% Displaying the lookup table
display('The lookip table is : ')
display(interval);
 
% Encoder Table
 
low = 0;
high = 1;
for i = 1 : len
   for j = 1 : len_unique
 
       % if the value from 'str'
       % matches with 'u' then
       if str(i) == u(j);
           pos = j;
           j = j + 1; 
 
           % displaying the matched length
           % of unique characters
           display(pos);
 
           % getting the tag value
           % of the matched character
           range = high - low;
           high = low + (range .* interval(pos, 2));
           low = low + (range .* interval(pos, 1));
           i = i + 1;
           break
       end
   end
end
 
% displaying tag value
tag = low;
display(tag);

Producción :

The entered string is : GeeksforGeeks
The length of the string is : 13
The unique characters are : Gefkors
The length of unique character string is : 7

z =

     2     4     1     2     1     1     2


p =

    0.1538    0.3077    0.0769    0.1538    0.0769    0.0769    0.1538


cpr =

    0.1538    0.4615    0.5385    0.6923    0.7692    0.8462    1.0000


newcpr =

         0    0.1538    0.4615    0.5385    0.6923    0.7692    0.8462    1.0000

The lookip table is : 

interval =

         0    0.1538
    0.1538    0.4615
    0.4615    0.5385
    0.5385    0.6923
    0.6923    0.7692
    0.7692    0.8462
    0.8462    1.0000


pos =

     1


pos =

     2


pos =

     2


pos =

     4


pos =

     7


pos =

     3


pos =

     5


pos =

     6


pos =

     1


pos =

     2


pos =

     2


pos =

     4


pos =

     7


tag =

    0.0409

Descodificación 

str = '';
 
for i = 1 : len
   for j = 1 : len_unique
      
       % If tag value falls between a certain
       % range in lookup table then
       if tag > interval(j, 1) && tag < interval(j, 2)
           pos = j;
           tag = (tag - interval(pos, 1)) / p(j);
 
           % Getting the matched tag
           % value character
           decoded_str = u(pos);
 
           % String concatenating
           % 'decoded_str' into 'str'
           str = strcat(str, decoded_str);
           break
       end
   end
end
 
% Displaying final decoded string
disp(str)

Producción :

GeeksforGeeks