Meilleur arbre Huffman pour une compression optimale

Question

Je coche un compresseur de chaîne Huffman et je voudrais avoir une confirmation que je fais la compression optimale avec mon arbre.

J'utilise ce genre d'arbre:

Au lieu de ce genre d'arbre:

Je pense que plus de 10 personnages uniques, il n'est pas possible de compresser sur 8 bits.

La première image est-elle vraiment optimale?

Answer 1

L'idée très basique est d'ajouter les deux plus petits nœuds, créant un nouveau nœud qui valeur est la somme de ses 2 enfants.

Le respect de cette règle à la racine de l'arbre garantit que l'arbre produit sera optimal.

Par conséquent, tu as aucun contrôle Sur la forme de l'arbre: cela dépend entièrement de la distribution de probabilité des caractères. Il peut finir par être un arbre dégénéré (une branche par niveau) si la distribution de probabilité ressemble à une série Fibonacci.

La création d'arbre Huffman avec une profondeur maximale prédéfinie est donc plus complexe et nécessite de briser la règle habituelle d'ajouter toujours les 2 nœuds les plus petits. L'arbre résultant ne sera évidemment pas optimal.