La codificación adaptativa de Huffman (también denominada codificación dinámica de Huffman ) es una técnica de codificación adaptativa basada en la codificación de Huffman . Permite construir el código a medida que se transmiten los símbolos, sin tener un conocimiento inicial de la distribución de la fuente, lo que permite la codificación de una pasada y la adaptación a las condiciones cambiantes de los datos. [1]
La ventaja del procedimiento de un solo paso es que la fuente se puede codificar en tiempo real, aunque se vuelve más sensible a los errores de transmisión, ya que una sola pérdida arruina todo el código.
Algoritmos
Hay una serie de implementaciones de este método, las más notables son FGK ( Faller - Gallager - Knuth ) y el algoritmo Vitter .
Algoritmo FGK
Es una técnica de codificación en línea basada en la codificación de Huffman. Al no tener un conocimiento inicial de las frecuencias de ocurrencia, permite ajustar dinámicamente el árbol de Huffman a medida que se transmiten los datos. En un árbol de FGK Huffman , se usa un nodo externo especial, llamado nodo 0 , para identificar un personaje recién llegado. Es decir, siempre que se encuentren nuevos datos, envíe la ruta al nodo 0 seguida de los datos. Para un personaje del pasado, simplemente muestre la ruta de los datos en el árbol actual de Huffman. Lo más importante es que tenemos que ajustar el árbol de FGK Huffman 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. Se logra mediante intercambios consecutivos de nodos, subárboles o ambos. El nodo de datos se intercambia con el nodo de mayor orden de la misma frecuencia en el árbol de Huffman (o el subárbol enraizado 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 tiene algunos inconvenientes sobre el intercambio de nodo o subárbol, Vitter propuso otro algoritmo para mejorarlo.
Algoritmo de Vitter
Algunas terminologías y limitaciones importantes: -
- Numeración implícita : simplemente significa que los nodos se numeran en orden creciente por nivel y de izquierda a derecha. es decir, los nodos del nivel inferior tendrán un número implícito bajo en comparación con los nodos del nivel superior y los nodos del mismo nivel se numerarán en orden creciente de izquierda a derecha.
- Invariante : Para cada peso w, todas las hojas de peso w preceden a todos los nodos internos que tienen peso w.
- Bloques : los nodos del mismo peso y del mismo tipo (es decir, nodo hoja o nodo interno) forman un bloque.
- Líder : nodo con el número más alto de un bloque.
Los bloques están interconectados por orden creciente de sus pesos.
Un bloque de hojas siempre precede al bloque interno del mismo peso, manteniendo así la invariante.
NYT (aún no transferido) es un nodo especial y se utiliza para representar símbolos que 'aún no se han transferido' .
algoritmo para agregar un símbolo es hoja_a_incremento: = NULL p: = puntero al nodo hoja que contiene el siguiente símbolo si (p es NYT) entonces Extienda p agregando dos hijos El hijo izquierdo se convierte en el nuevo NYT y el hijo derecho es el nuevo nodo de la hoja del símbolo p : = padre del nuevo nodo hoja de símbolo leaf_to_increment: = Hijo derecho de p demás Intercambia p con el líder de su bloque si (el nuevo p es hermano de NYT) entonces hoja_a_incremento: = p p : = padre de p mientras que (p ≠ NULL) no Slide_And_Increment (p) if (leaf_to_increment! = NULL) entonces Slide_And_Increment (hoja_a_incremento)
función Slide_And_Increment (p) es previous_p: = padre de p si (p es un nodo interno) entonces Deslice p en el árbol más alto que los nodos de las hojas de peso wt + 1 aumentar el peso de p en 1 p : = previous_p else Deslice p en el árbol más alto que los nodos internos de peso wt aumentar el peso de p en 1 p : = nuevo padre de p .
El codificador y el descodificador comienzan solo con el nodo raíz, que tiene el número máximo. Al principio es nuestro nodo NYT inicial.
Cuando transmitimos un símbolo NYT, tenemos que transmitir código para el nodo NYT, luego para su código genérico.
Para cada símbolo que ya está en el árbol, solo tenemos que transmitir código para su nodo hoja.
Ejemplo
La codificación "abb" da 01100001 001100010 11.
Paso 1:
Empiece con un árbol vacío.
Para "a" transmite su código binario.
Paso 2:
NYT genera dos nodos secundarios: 254 y 255, ambos con peso 0. Aumente el peso para la raíz y 255. El código para "a", asociado con el nodo 255, es 1.
Para "b" transmita 0 (para el nodo NYT) y luego su código binario.
Paso 3:
NYT genera dos nodos secundarios: 252 para NYT y 253 para nodo hoja, ambos con peso 0. Aumente los pesos para 253, 254 y raíz. Para mantener el invariante de Vitter de que todas las hojas de peso w preceden (en la numeración implícita) a todos los nodos internos de peso w, la rama que comienza con el nodo 254 debe intercambiarse (en términos de símbolos y pesos, pero no de orden numérico) con el nodo 255. El código para "b" es 11.
Para la segunda "b" transmita 11.
Para facilitar la explicación, este paso no sigue exactamente el algoritmo de Vitter, [2] pero los efectos son equivalentes.
Paso 4:
Vaya al nodo hoja 253. Observe que tenemos dos bloques con peso 1. El nodo 253 y el 254 es un bloque (que consta de hojas), el nodo 255 es otro bloque (que consta de nodos internos). Para el nodo 253, el número más grande en su bloque es 254, así que intercambie los pesos y símbolos de los nodos 253 y 254. Ahora el nodo 254 y la rama que comienza desde el nodo 255 satisfacen la condición SlideAndIncrement [2] y por lo tanto deben intercambiarse. Por último, aumente el peso de los nodos 255 y 256.
El código futuro para "b" es 1, y para "a" ahora es 01, lo que refleja su frecuencia.
Referencias
- ^ Ze-Nian Li; Mark S. Drew; Jiangchuan Liu (9 de abril de 2014). Fundamentos de Multimedia . Springer Science & Business Media. ISBN 978-3-319-05290-8.
- ^ a b "Codificación adaptativa de Huffman" . Cs.duke.edu . Consultado el 26 de febrero de 2012 .
- Artículo original de Vitter: JS Vitter, " Diseño y análisis de códigos dinámicos de Huffman ", Journal of the ACM, 34 (4), octubre de 1987, págs. 825–845.
- JS Vitter, "ALGORITHM 673 Dynamic Huffman Coding", ACM Transactions on Mathematical Software, 15 (2), junio de 1989, págs. 158-167. También aparece en los algoritmos recopilados de ACM.
- Donald E. Knuth, "Codificación dinámica de Huffman", Journal of Algorithm, 6 (2), 1985, págs. 163–180.
enlaces externos
- Este artículo incorpora material de dominio público del documento NIST : Black, Paul E. "codificación adaptativa de Huffman" . Diccionario de algoritmos y estructuras de datos .
- Sitio de Dan Hirschberg de la Universidad de California
- Sitio del Dr. David Marshall de la Universidad de Cardiff
- Implementación en C del algoritmo de Vitter
- Excelente descripción de la Universidad de Duke