霍夫曼算法贪婪属性的证据如何以最佳的树t开始？

Question

在本文 1，索引1表示 x 和 y 是最小概率，并且有最佳的代码树，其中两个字符是最大深度的兄弟姐妹。在证明该声明中，作者从树 T 开始，其在最大景深处具有 B 和 C 。我无法理解为什么树 t 是最佳的，因为如果 x 和 y 具有最小的概率，则树t不能是最佳的，因为霍夫曼算法不会构建这样的树。我认为我的问题在这里是以了解最佳树的意思。

如果有人来自CSLR，这就是关于LEMMA 16.2和证明。

Answer 1

代码树是最佳如果平均码字长度是最小的。这与霍夫曼的算法无关。霍夫曼的算法保证生成最佳的代码树，但可能有其他代码树。事实上，霍夫曼的算法可以使用不同的绑定规则产生不同的代码树。此外，也可以使用霍夫曼的算法生产每个最佳码树，即使是任意的绑定规则也是如此。

这是一个最佳代码树的正式定义。让 $ \ pi $ 是分发。代码树的 $ \ pi $ -cost 是码字的预期长度，其中遵守 $ \ pi $ 。代码树是 <跨越类=“math-container”> $ \ pi $ 如果它 $ \ pi $ -cost等于最小 $ \ pi $ -cost的任何代码树。