首页 > 代码库 > 证明哈夫曼编码是最优的

证明哈夫曼编码是最优的

2024-08-02 21:51:24   219人阅读



改编自下面是证明链接（英文）

http://algoviz.org/OpenDSA/Books/OpenDSA/html/HuffProof.html

====================

设buildHuff是创建哈夫曼树的函数。


引理1：给定W = {w1, w2, w3...,wn} (n >= 2), 以此集合构建相应的哈夫曼树。令wi, wj 是W中权重最小的两个元素，则这两个数对应的结点是兄弟结点，且这两结点在二叉树中的深度大小于等于其它任何一个叶结点的深度。

证明：由哈夫曼树的构建过程可知，wi, wj 所在结点是兄弟结点（在不影响阅读的前提下，以wi, wj 指代这两个结点）。假设在哈夫曼树中，wi, wj 所在结点的深度不是最深的，则哈夫曼树应似图1 样式，存在一些结点，其深度大于wi, wj 的深度。在图1中，wi, wj的父结点U的权重应大于结点X权重，否则构建哈夫曼树时，应选择V而不是X作为U的子结点。但这是不可能的，因为由假设知wi, wj是W中权重最小的两个元素。得出矛盾，问题得证。


图1 An impossible Huffman tree, showing the situation where the two nodes with least weight,wi and wj are not the deepest nodes in the tree. Triangles represent subtrees.

定理1：哈夫曼树是最优的。

证明：用归纳法证明。

  • 基本情部分: 当 n=2 时, 哈夫曼树具有最小权重外部路径（WPL），因为树 仅有二种可能，有二个叶结点的二种哈夫曼树下的WPL是相同的。
  • 假设: 设有哈夫曼树有 n?1 个叶子时，定理成立。
  • 推导: 令T为有n （n>=2）个叶子的哈夫曼树。不失 一般性，设  w 1 ≤w 2 ≤...≤w n  。令V 是w 1  与 w 2   的父结点。由引理1知, 在T中，不存在叶结点，其深度大于叶结点 w 1   与 w 2  的深度。如果这样的结点存在，则我们可以通过把他们与w1或w2交换，减小WPL。但由引理1知，这样的叶结点是不在的。称T‘是与T相同的哈夫曼树，除非将结点V替换为结点V‘, 其中V‘的权重是w1+w2。根据归纳假设，T是最优的（WPL最小）。
  • . If any other leaf nodes in the tree were deeper, we could reduce their weighted path length by swapping them withw 1   or w 2  . But the lemma tells us that no such deeper nodes exist. Call T ′   the Huffman tree that is identical to T  except that node V  is replaced with a leaf node V ′   whose weight is w 1 +w 2  . By the induction hypothesis, T ′   has minimum external path length. Returning the children to V ′   restores tree T , which must also have minimum external path length.


    （注意：哈夫曼编码是最优之一。）

    • 证明哈夫曼编码是最优的


    联系
    我们