一个数据文件包含一个 8 位字符序列,因此所有 256 个字符大致相同:最大字符频率小于最小字符频率的两倍。证明这种情况下的霍夫曼编码并不比使用普通的 8 位定长编码更有效。
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。
这有点非正式,更像是一个草图而不是一个证明,但它应该足以让你写一些更正式的东西。