greedy - 霍夫曼编码在 8 位序列上证明

Question

一个数据文件包含一个 8 位字符序列，因此所有 256 个字符大致相同：最大字符频率小于最小字符频率的两倍。证明这种情况下的霍夫曼编码并不比使用普通的 8 位定长编码更有效。

Answer 1

证明是直接的。假设 wlog 字符按频率升序排序。我们知道f(1)和f(2)会先join到f'(1)中，因为f(2) >= f(1) and 2*f(1) > f(256)，这个就赢了' 直到 f(256) 与某物连接后才被连接。同理，f(3) 和 f(4) 将连接到 f'(2) 中，其中 f'(2) >= f'(1) > f(256)。这样继续下去，我们得到 f(253) 和 f(254) 加入到 f'(127) >= ... >= f'(1) > f(256) 中。最后，f(255) 和 f(256) 连接成 f'(128) >= f'(127) >= ... >= f'(1)。我们现在认识到，由于 f(256) < 2*f(1) <= f'(1) 和 f'(128) <= 2*f(256)，f'(128) <= 2*f(256 ) < 4*f(1) <= 2*f'(1)。因此，f'(128) < 2*f'(1)，

由于该条件在这一轮中成立，因此可以直截了当地说，它同样适用于所有轮次。Huffman 将执行 8 轮，直到所有节点都连接到一个根节点 (128, 64, 32, 16, 8, 4, 2, 1)，此时算法将终止。由于在每个阶段，每个节点都连接到另一个节点，在这一点上，Huffman 算法接受了相同的处理，树的每个分支将具有相同的长度：8。

这有点非正式，更像是一个草图而不是一个证明，但它应该足以让你写一些更正式的东西。