Codificación adaptativa de Huffman

Se trata de una técnica de codificación en línea basada en la codificación de Huffman. Al no requerir conocimiento previo de las frecuencias de ocurrencia, permite ajustar dinámicamente el árbol de Huffman a medida que se transmiten los datos. En un árbol de Huffman FGK, se utiliza un nodo externo especial, denominado nodo 0 , para identificar un nuevo carácter. Es decir, cada vez que se encuentran nuevos datos, se genera la ruta al nodo 0 seguida de los datos. Para un carácter que ya ha llegado, simplemente se genera la ruta de los datos en el árbol de Huffman actual. Lo más importante es que debemos ajustar el árbol de Huffman FGK si es necesario y, finalmente, actualizar la frecuencia de los nodos relacionados. A medida que aumenta la frecuencia de un dato, la propiedad de hermanos del árbol de Huffman puede romperse. El ajuste se activa por este motivo y se logra mediante intercambios consecutivos de nodos, subárboles o ambos. El nodo de datos se intercambia con el nodo de mayor orden con la misma frecuencia en el árbol de Huffman (o con el subárbol con raíz en el nodo de mayor orden). Todos los nodos ancestros del nodo también deben procesarse de la misma manera.

Dado que el algoritmo FGK presenta algunos inconvenientes en lo que respecta al intercambio de nodos o subárboles, Vitter propuso otro algoritmo para mejorarlo.

Algunos términos y limitaciones importantes  :

• Numeración implícita  : Significa que los nodos se numeran en orden ascendente por nivel y de izquierda a derecha. Es decir, los nodos del nivel inferior tendrán un número implícito menor que los nodos del nivel superior, y los nodos del mismo nivel se numeran en orden ascendente de izquierda a derecha. En otras palabras, al construir el árbol de Huffman, al fusionar dos nodos en un nodo padre, se asigna el nodo con el valor más bajo como hijo izquierdo y el nodo con el valor más alto como hijo derecho.
• Invariante  : Para cada peso w, todas las hojas de peso w preceden a todos los nodos internos que tengan peso w. En otras palabras, cuando construimos el árbol de Huffman, si varios nodos tenían el mismo valor, priorizamos la fusión de las hojas sobre los nodos internos.
• Bloques  : Los nodos del mismo peso y del mismo tipo (es decir, nodos hoja o nodos internos) forman un bloque.
• Líder  : Nodo con el número más alto en un bloque.

Los bloques están interconectados en orden creciente de sus pesos.

Un bloque hoja siempre precede a un bloque interno del mismo peso, manteniendo así la invariante.

NYT (Not Yet Transferred) es un nodo especial que se utiliza para representar símbolos que "aún no se han transferido" .

El algoritmo para agregar un símbolo es hoja_a_incrementar := NULL p := puntero al nodo hoja que contiene el siguiente símbolo si (p es NYT) entonces Extiende p añadiendo dos hijos El hijo izquierdo se convierte en el nuevo NYT y el hijo derecho es el nuevo símbolo del nodo hoja. p := padre del nuevo símbolo nodo hoja hoja_a_incrementar := Hijo derecho de p demás Intercambia p con el líder de su bloque. si (el nuevo p es hermano del NYT) entonces hoja_a_incrementar := p p := padre de p mientras (p ≠ NULL) hacer Deslizar_y_incrementar(p) Si (leaf_to_increment != NULL) entonces Slide_And_Increment(leaf_to_increment)

La función Slide_And_Increment(p) es previous_p := padre de psi (p es un nodo interno) entonces Desliza p en el árbol más arriba que los nodos de las hojas de peso wt + 1 aumentar el peso de p en 1 p := previous_p de lo contrario Desliza p en el árbol más arriba que los nodos internos de peso wt aumentar el peso de p en 1 p := nuevo padre de p .

El codificador y el decodificador comienzan únicamente con el nodo raíz, que es el que tiene el número máximo. Al principio, se trata de nuestro nodo inicial NYT.

Cuando transmitimos un símbolo del NYT, tenemos que transmitir primero el código del nodo del NYT y luego su código genérico.

Para cada símbolo que ya se encuentra en el árbol, solo tenemos que transmitir el código correspondiente a su nodo hoja.