Confus au sujet de Huffman Arbres

Question

un tutoriel rapide sur la génération d'un arbre de Huffman

Confus au sujet de Huffman arbres. Vers la fin de ce lien ci-dessus, il montre l'arbre avec 2 éléments de gauche, puis l'arbre terminé. Je suis confus au sujet de la façon dont il est dérivé. Est-il un moyen spécifique a besoin d'arbres huffman à être ramifiés?

Par exemple, 57: * avec son enfant droit 35: * est bifurqué à droite. Aurait-il été 35 ramifié à gauche avec 22 ramifiée à droite? En outre, pourquoi pas 22: * jumelé avec 15: 4 - juste jumelé avec 20:. 5 pour créer un nouvel arbre

De obersvations initiales, il semble que l'arbre n'a pas besoin d'être équilibré ou avoir un ordre spécifique autre que les fréquences d'une feuille ajouter à la valeur du nœud parent. Deux personnes pourrait créer un arbre huffman avec les mêmes données finissent avec différentes valeurs de codage?

Answer 1

La clé des arbres Huffman est la suivante:

Trier cette liste par la fréquence et de faire les deux plus bas éléments dans les feuilles

Si vous avez plus de deux éléments qui ont la fréquence la plus basse (par exemple 3,4,4 ...), tout deux fera (3 et l'une des 4 s - pas deux 4s). En outre, il est important de ne pas lequel de ces éléments les plus bas est attribué 0 et qui est 1. Ces deux faits permettent différents encore valides encodages Huffman proviennent de la même données.

L'arbre de Huffman est censé être équilibré par des fréquences, et non par le nombre de nœuds. Ainsi, le suivant est équilibré:

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

et ce n'est pas:

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

Plus précisément dans votre question, 15 est associé à 20 et non 22 parce que 15 et 20 sont les deux autres valeurs les plus faibles (à la fois inférieur à 22). Soit branchement (gauche ou droite) aurait été bien, tant qu'il est cohérent (toujours inférieur gauche, ou toujours plus petit droit, dans le même algorithme, de sorte que le codage peut être reconstruit à l'autre bout).

Answer 2

Les messages à ce jour sont faux et trompeurs. Le choix des feuilles avec des poids égaux Finalité matière et ils ne changent comment ils compressent les données

Voici un exemple de compteur qui montre comment différents choix conduisent à des taux de compression: ABBBCCCDDDDEEEEEEEE

A: 1, B: 3, C 3, D 4, E: 8. Première étape: prendre A et B pour former un noeud avec un poids 4. Deuxième étape:

Si vous prenez le nouveau nœud dans la première étape avec C, alors vous obtenez (19 (11 (7 (4 (1-A) (3-B)) (3-C)) (4-D)) (8-E)) qui fournit des données compressées 37 bits.

Si, d'autre part, vous prenez D, qui a aussi le poids 4, au lieu du nœud nouvellement créé, vous obtenez (19 (11 (4 (1-A) (3-B)) (7 (3-C) (4-D))) (8-E)) qui fournit des données compressées 41 bits.

Answer 3

Tout est expliqué sur la page. 22: * n'a pas été couplé avec 15: 4 parce que, dans chaque étape, deux noeuds avec les éléments les plus bas sont combinés. Cela crée un ordre unique.

codes de Huffman peut être différent (si vous avez plusieurs valeurs avec la même fréquence ou l'échange 0 et 1 représentation de gauche / droite), mais les longueurs huffman ne peut pas être.

La ramification gauche / droite est juste une question de savoir comment dessiner l'arbre ou le représenter graphique, donc cela n'a pas d'importance.