Confundido sobre los árboles de Huffman

Question

Un tutorial rápido sobre la generación de un árbol de Huffman

Confundido sobre los árboles de Huffman. Cerca del final de ese enlace anterior, muestra el árbol con 2 elementos restantes, y luego el árbol completado. Estoy confundido sobre la forma en que está ramificada. ¿Hay una forma específica en que un árbol de Huffman necesita estar ramificado?

Por ejemplo, 57:* con su hijo derecho 35:* está ramificada a la derecha. ¿Podría haber sido 35 ramificado a la izquierda con 22 ramificados a la derecha? Además, ¿por qué no fue 22?* Emparejado con 15: 4: se combinó con 20: 5 para crear un nuevo árbol.

De las obervaciones iniciales, parece que el árbol no necesita ser equilibrado o tener ningún orden específico que no sea que las frecuencias de una hoja se suman al valor del nodo principal. ¿Podrían dos personas que crean un árbol Huffman con los mismos datos terminar con diferentes valores de codificación?

Answer 1

La clave para los árboles de Huffman es esta:

Ordene esta lista por frecuencia y haga Elementos dos más bajos en hojas

Si tiene más de dos elementos que tienen la frecuencia más baja (por ejemplo, 3,4,4 ...), cualquiera de los dos funcionará (3 y cualquiera de los 4s, no dos 4). Además, no es importante cuáles de estos elementos más bajos se asignan 0 y cuáles son 1. Estos dos hechos permiten que surgen codificaciones de Huffman diferentes pero válidas que surjan de los mismos datos.

Se supone que el árbol Huffman está equilibrado por frecuencias, no por el número de nodos. Por lo tanto, lo siguiente está equilibrado:

(100 (50 (25 (12 (12 1)))))

Y esto no es:

(((100 50) 25) ((12 12) 1)))

Específicamente en su pregunta, 15 se combina con 20 y no 22 porque 15 y 20 son los dos valores más bajos restantes (ambos inferiores a 22). La ramificación (izquierda o derecha) habría estado bien, siempre que sea consistente (siempre más pequeña izquierda, o siempre más pequeña, la derecha, dentro del mismo algoritmo, para que la codificación pueda reconstruirse en el otro extremo).

Answer 2

Las publicaciones hasta ahora son incorrectas y engañosas: la elección de las hojas con peso igual. lo hace importa y cambian lo bien que comprimen los datos.

Aquí hay un ejemplo de contador que demuestra cómo las diferentes opciones conducen a diferentes tasas de compresión: AbbCCCDDDDDEEEEEEEE

A: 1, B: 3, C: 3, D: 4, E: 8. Primer paso: tome A y B para formar un nodo con peso 4. Segundo paso:

Si toma el nodo recién creado en el primer paso con C, entonces obtiene(19 (11 (7 (4 (1-A) (3-B)) (3-C)) (4-D)) (8-E)) que proporciona datos comprimidos de 37 bits.

Si, por otro lado, tomas D, que también tiene el peso 4, en lugar del nodo recién creado, obtienes(19 (11 (4 (1-A) (3-B)) (7 (3-C) (4-D))) (8-E)) que proporciona datos comprimidos de 41 bits.

Answer 3

Todo se explica en la página. 22:* no se combinó con 15: 4 porque en cada paso, se combinan dos nodos con los elementos más bajos. Esto crea un orden único.

Los códigos de Huffman pueden ser diferentes (si tiene múltiples valores con la misma frecuencia o intercambio 0 y 1 representación de izquierda/derecha), pero las longitudes de Huffman no pueden ser.

La ramificación a la izquierda/derecha es solo una cuestión de cómo dibujar el árbol o representarlo gráfico, por lo que esto no importa.