Comment la preuve de la propriété gourmande d'algorithme Hoffman commence par un arbre optimal T?

Question

dans Ce papier la revendication 1 indique que x et y sont la plus faible probabilité et il y a une arborescence de code optimale dans laquelle ces deux caractères sont des frères et sœurs à la profondeur maximale .En preuve de cette réclamation, l'auteur commence par l'arborescence t qui a b et c à la profondeur maximale de l'arbre.Je ne peux pas comprendre pourquoi l'arbre t est appelé optimal, car si x et y ont des probabilités les plus petites, puis l'arbre t ne peut pas être optimal parce que HoffmanL'algorithme ne construira pas un tel arbre.Je pense que mon problème ici est de comprendre ce que signifie un arbre optimal.

Si quelqu'un vient de CSLR, il s'agit de lemme 16.2 et de preuve à cela.

Answer 1

Un arbre de code est optimal si la longueur moyenne du mot de code est minime. Cela n'a rien à voir avec l'algorithme de Huffman. L'algorithme de Huffman est garanti de produire un arbre de code optimal, mais il pourrait y avoir d'autres arbres de code. En fait, l'algorithme de Huffman pourrait produire des arbres de code différents en utilisant différentes règles de cravate. De plus, tous les arbres de code optimaux peuvent ne pas être produits à l'aide d'un algorithme Huffman, même avec une règle de cravate arbitraire.

Voici une définition formelle d'un arbre de code optimal. Laissez $ \ pi $ être une distribution. $ \ pi $ -cost d'un arbre de code est la longueur attendue d'un mot de code, où l'attente est prise en ce qui concerne $ \ PI $ . Un arbre de code est optimal pour $ \ pi $ si sa $ \ pi $ -Cost est égal au minimum $ \ pi $ -cost de n'importe quel arborescence de code.