algorithm - 霍夫曼最小方差编码

Question

众所周知，具有最小方差的霍夫曼代码是可取的。我已经浏览了整个波兰语/英语互联网，这就是我发现的：要构建具有最小方差的霍夫曼代码，您需要使用以下方法之一打破联系（当然节点的概率是最重要的）：

• 选择代表最短树的节点
• 选择最早创建的节点（考虑在开始时创建的叶子）。

问题是，我找不到任何这些方法正确性的证据。有人可以证明这些吗？

我很乐意澄清任何事情。

Answer 1

一些系统比“当有平局时，做出最小化树的最大深度的选择”具有更强的约束——它们对树的最大深度设置了一个硬限制（长度限制，也称为最小方差 Huffman编码）：

• “不管有没有平局，构建一个最大深度最多为16步的树，因此最大码字长度为16位”（如JPEG图像压缩中使用的霍夫曼编码）（Jpeg霍夫曼编码程序）

• “无论有没有平局，构建一个最大深度最多为 15 步的树，因此最大码字长度为 15 位”（如DEFLATE 中使用的Huffman 码和 gzip 中使用的 Huffman 码

• “不管有没有平局，构建一个最大深度最多为12步的树，因此最大码字长度为12位”（“Huff0使用12位限制。”）

我的理解是，人们已经开发了几种启发式算法来限制霍夫曼码字长度，这些算法可以正常工作，但是启发式算法并不总是能提供最好的压缩。

有几个人提到“最佳长度限制霍夫曼码”，显然存在不止一种算法来找到它们：

• Lawrence L. Larmore 和 Daniel S. Hirschberg。“最佳长度限制霍夫曼码的快速算法”
• “最佳长度限制霍夫曼码”
• “最佳长度限制霍夫曼码的快速算法”