Codificación y decodificación adaptativa de Huffman

Requisito previo: codificación Huffman , decodificación Huffman 
La codificación Huffman adaptativa también se conoce como codificación Huffman dinámica. La implementación se realiza mediante el algoritmo de Vitter. 
 

Codificación

Codificación adaptativa de Huffman para una string que contiene alfabetos: 
Sea m el número total de alfabetos. Entonces m = 26. 
Para el algoritmo de Vitter, encuentre los parámetros e & r tales que 
 

m = 2e + r and 0 ≤ r ≤ 2e
Therefore, for m = 26 we get e = 4 & r = 10

Hay dos tipos de código NYT Code y Fixed Code. 
 

NYT code = Traversing tree from the root node to that particular NYT node.

Para el código fijo, se puede calcular a partir de las siguientes dos condiciones: 
 

1. Si 0 ≤ k ≤ 2r Entonces la letra Sk se codifica como la representación binaria de (k-1) en (e+1) bits. (donde k es la posición del alfabeto en orden ordenado)
2. De lo contrario, la letra Sk se codifica como la representación binaria de (kr-1) en e bits.

Actualización del árbol 
La actualización del árbol en el algoritmo Vitter sigue la numeración implícita. En numeración implícita, 
 

• Los Nodes se numeran en orden creciente, es decir, por nivel y de izquierda a derecha.
• Los Nodes que tienen el mismo peso y el mismo tipo juntos forman un bloque
• Los bloques están relacionados entre sí por orden creciente de sus pesos
• El Node interno está representado por una forma ovalada. Peso de los Nodes internos = Suma de los pesos de los Nodes secundarios
• El Node externo está representado por una forma cuadrada. Peso de los Nodes externos = Inicialmente 1 y, si se repite, aumenta el peso en 1

Pasos para la actualización del árbol: 
 

1. Inicialice el árbol con el Node NYT
2. Para que un símbolo se reconozca por primera vez, el Node NYT inicial se divide en un Node NYT y el nuevo Node se inicializa con ese símbolo y peso = 1.
3. Asigne la suma del peso de los Nodes secundarios al Node principal
4. Si se encuentra un símbolo repetido, los pesos se actualizan a ese símbolo.

Nota: durante la actualización en el árbol, si el peso del subárbol izquierdo es mayor que el del subárbol derecho, entonces se deben intercambiar los Nodes. 

Ejemplo 
 

code = "aardvark"
The final Code we get is:
00000 1 010001 0000011 0001011 0 10  110001010
  a   a   r      d        v    a  r     k

Explicación: 
Para el código de string = «oso hormiguero», e = 5, r = 10 
Como se muestra en la imagen de arriba, el árbol se inicializa con el Node NYT con peso 0. 
 

1. Para el símbolo ‘a’, k = 1. 
    

NYT Code = "" (initially tree is empty)

1. Para código fijo: como k < 2r, es decir, 1 < 2*10, satisface la condición (1) 
   Entonces, el código fijo es una representación binaria de (k-1) = 0 como una representación de 5 bits 
    

Fixed Code = "00000"

1.  

Huffman Code for symbol for 'a' is "00000"

1.  
2. Para el símbolo ‘a’ que ya existe en el árbol. Atravesando Tree hasta el símbolo ‘a’, obtenemos el código = «1» 
    

Huffman Code for symbol for 'a' is "1"

1. Para el símbolo ‘r’, k = 18. 
    

NYT Code = "0" (traversing up to NYT Node)

1. Para código fijo: si k > 2r, es decir, 18 > 2*10, cumple la condición (2), 
   por lo que el código fijo es una representación binaria de (k-1 = 17) como una representación de 5 bits 
    

Fixed Code = "10001"

1.  

Huffman Code for symbol for 'r' is "010001"

1. Para el símbolo ‘d’, k = 4. 
    

NYT Code = "000" (traversing up to NYT Node)

1. Para código fijo: como k < 2r, es decir, 4 < 2*10, satisface la condición (1) 
   Entonces, el código fijo es una representación binaria de (k-1 = 3) como una representación de 5 bits 
    

Fixed Code = "00011"

1.  

Huffman Code = "00000011"

1. Para el símbolo ‘v’, k = 22. 
    

NYT Code = "000" (traversing up to NYT Node)

1. Para código fijo: como k > 2r, es decir, 22 > 2*10, cumple la condición (2) 
   Por lo tanto, el código fijo es una representación binaria de (kr-1 = 11) como una representación de 4 bits 
    

Fixed Code = "1011"

1.  

Huffman Code = "0001011"

1. Intercambie el Node del subárbol izquierdo y derecho ya que el árbol está violando la propiedad
2. Para el símbolo ‘a’ que ya existe en el árbol. Atravesando el árbol hasta el símbolo ‘a’, obtenemos el código = «0» 
    

Huffman Code for symbol for 'a' is "0"

1. Para el símbolo ‘r’ que ya existe en el árbol. Atravesando el árbol hasta el símbolo ‘a’, obtenemos el código = «10» 
    

Huffman Code for symbol for 'r' is "10"

1. Para el símbolo ‘k’, k = 11. 
    

NYT Code = "1100" (traversing up to NYT Node)

1. Para código fijo: como k < 2r, es decir, 11 < 2*10, satisface la condición (1) 
   Entonces, el código fijo es una representación binaria de (k-1 = 10) como una representación de 5 bits 
    

Fixed Code = "01010"

1.  

Huffman Code for symbol for 'r' is "110001010"

Descodificación

Pasos para decodificar: 

1. Leer string binaria
2. Si el Node hoja encontrado es NYT 
   • Lea los siguientes bits 
     1. Si el valor de e bit < r, entonces para obtener el símbolo requerido, convierta (e+1) bits al valor decimal de (e+1) bits + 1
     2. Si el valor de e bit > r, entonces, para obtener el símbolo requerido, convierta e bits al valor decimal de e bits + r + 1

Ejemplo: 
 

code = "00000101000100000110001011010110001010"
We get final decoded code as
 00000  1   0    10001  00   00011  000  1011  0  10  1100  01010
   a    a  NYT     r    NYT    d    NYT   v    a   r   NYT    k

Explicación: 
 

• Comience a decodificar leyendo los primeros bits e. Entonces los primeros 4 bits son 0000, convirtiéndose en decimal = 0. 
  Ahora el valor 0 < r , es decir, 0 < 10 satisface la condición (1). 
  Ahora, de acuerdo con la condición (1), convierta primero e+1 = 5 bits en decimal y agréguele 1. 
   

00000 = 0
0 + 1 = 1, which is value for alphabet a.

• Actualice el árbol y agregue un Node para el símbolo ‘a’ en el árbol
• Lea el siguiente bit en el código dado y recorra el árbol. Llegamos al Node de la hoja externa ‘a’. Entonces, el siguiente símbolo decodificado es ‘a’.
• Lea el siguiente conjunto de bits del código dado y recorra el árbol. Tenemos 0 como Node NYT. Después de llegar al Node NYT, lea e bits que son 1000. Convierta 1000 a decimal es 8. Como 8 < r satisface la condición (1). 
  Ahora convierta e+1 bits en decimal y agréguele 1. 
   

10001 = 17
17 + 1 = 18, which is value for alphabet r.

• Actualice el árbol y agregue un Node para el símbolo ‘r’ en el árbol.
• Al leer el siguiente conjunto de bits y atravesar el árbol, llegamos al Node NYT en 00. Lea e bits que son 0001. Convierta 0001 en decimal es 1. Como 1 < r satisface la condición (1). 
  Ahora convierta e+1 bits en decimal y agréguele 1. 
   

00011 = 3
3 + 1 = 4, which is value for alphabet d.

• Actualice el árbol y agregue un Node para el símbolo ‘d’ en el árbol.
• Al leer el siguiente conjunto de bits y atravesar el árbol, llegamos al Node NYT en 000. Lea los bits e que son 1011. Convierta 1011 en decimal es 11. Como 11> r satisface la condición (2). 
  Ahora convierta k+r+1 bits en decimal y decodifique el símbolo. 
   

10110 = 22, which is value for alphabet v.

• Actualice el árbol y agregue un Node para el símbolo ‘v’ en el árbol.
• Al leer el siguiente conjunto de bits y atravesar el árbol, obtenemos el símbolo ‘a’ en 0. Actualice el árbol y agregue un Node para el símbolo ‘a’ en el árbol.
• Al leer el siguiente conjunto de bits y atravesar el árbol, obtenemos el símbolo ‘r’ en 10. Actualice el árbol y agregue un Node para el símbolo ‘a’ en el árbol.
• Al leer el siguiente conjunto de bits y atravesar el árbol, llegamos al Node NYT en 1100. Lea los bits e que son 0101. Convierta 0101 en decimal es 9. Como 9 < r satisface la condición (1). 
  Ahora convierta e+1 bits en decimal y agréguele 1. 
   

01000 = 8, 
8 + 1 = 9. which is value for alphabet k.

• Actualice el árbol y agregue un Node para el símbolo ‘v’ en el árbol.