Le codage de Huffman est basé sur ce que l'on appelle l'approche gloutonne ou la programmation dynamique.

Question

Peut-on résoudre le problème du codage de Huffman en utilisant la programmation dynamique, y a-t-il un algorithme ?

Answer 1

Le codage de Huffman fonctionne en créant un arbre binaire de nœuds. Ceux-ci peuvent être stockés dans un tableau régulier, dont la taille dépend du nombre de symboles, n. Le codage de Huffman peut être mis en œuvre dans les programmes suivants O(n logn) temps en utilisant le Greedy Algorithm approche. Le codage de Huffman ne convient pas à une solution de programmation dynamique, car le problème ne contient pas de sous-problèmes qui se chevauchent.

Answer 2

D'après mes connaissances en algorithmes, je crois que le codage de Huffman est basé sur l'approche Greedy. Comme nous le faisons dans le problème de sélection des activités. La planification des tâches et le problème du sac à dos en sont d'autres exemples.

Answer 3

[ Mise à jour ] : Je pense que la solution que je mentionne ci-dessous génère un code préfixe optimal, mais pas nécessairement identique au code Huffman. Le code Huffman, par définition, est généré en adoptant une approche avide. Bien qu'elle soit optimale, ce n'est pas la seule solution. (Par exemple, une fois que l'arbre de Huffman est généré, vous pouvez interchanger les feuilles dans le même niveau pour leur donner des codes différents tout en restant optimal).

---

Je pense que ce problème peut être résolu en utilisant la programmation dynamique, même si ce n'est pas très efficace. L'approche est ici très similaire à la recherche de l'arbre de recherche binaire optimal, puisque chaque fois que vous descendez d'un niveau, vous ajoutez un bit supplémentaire aux feuilles.

Ici est le lien permettant au code de calculer le nombre minimal de bits totaux. Bien sûr, c'est exponentiel, mais si vous utilisez DP, cela peut être résolu en temps O(n^2). Je n'ai pas essayé de générer le codage, mais cela devrait être possible je pense.