Confundido sobre Huffman árboles

Question

A quick tutorial on generating a huffman tree

Confundido sobre Huffman árboles. Cerca del final de ese enlace de arriba, muestra el árbol con 2 elementos restantes, y luego el árbol completo. Estoy confundido sobre la forma en que está ramificado. ¿Hay alguna forma específica de ramificación de un árbol huffman?

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

A partir de las observaciones iniciales, parece que el árbol no necesita estar equilibrado o tener un orden específico distinto de que las frecuencias de una hoja sumen el valor del nodo padre. ¿Podrían dos personas crear un árbol huffman con los mismos datos y tener diferentes valores de codificación?

Answer 1

La clave de árboles de Huffman es la siguiente:

ordenar esta lista por frecuencia y hacer las dos de menor elementos en hojas

Si usted tiene más de dos elementos que tienen la la frecuencia más baja (por ejemplo, 3,4,4 ...), cualquiera de dos hará (3 y cualquiera de 4s - no dos 4s). Además, no es importante a cuál de estos elementos más bajos se le asigna 0 y cuál es 1. Estos dos hechos permiten que surjan codificaciones de Huffman diferentes pero válidas a partir de los mismos datos.

Se supone que el árbol Huffman está equilibrado por las frecuencias, no por el número de nodos. Así, la siguiente es equilibrada:

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

y esto no es:

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

Específicamente en su pregunta, 15 se empareja con 20 y no 22 porque 15 y 20 son los dos valores restantes más bajos (tanto menor que 22). Cualquiera de las ramificaciones (izquierda o derecha) habría estado bien, siempre y cuando sea consistente (siempre más pequeño a la izquierda o siempre más pequeño a la derecha dentro del mismo algoritmo, de modo que la codificación se pueda reconstruir en el otro extremo).

Answer 2

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

Los códigos de Huffman pueden ser diferentes (si tiene múltiples valores con la misma frecuencia o intercambia 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 en forma gráfica, por lo que no importa.

Answer 3

Las publicaciones hasta el momento son erróneas y engañosas: la elección de las hojas con pesos iguales hace y cambian la forma en que comprimen los datos.

Aquí está un ejemplo contrario que demuestra cómo las diferentes opciones conducen a diferentes tasas de compresión: ABBBCCCDDDDEEEEEEEE

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 se toma el nodo recién creado en el primer paso con C, entonces se obtiene (19 (11 (7 (4 (1-A) (3-B)) (3-C)) (4-D)) (8-E)) que da 37-bits de datos comprimidos.

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