algorithm - 霍夫曼最小方差编码

Question

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

• 选择代表最短树的节点
• 选择最早创建的节点(将叶子视为在开始时创建)。

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

我很乐意澄清任何事情。

Answer 1

有些系统的约束比 “当出现平局时，做出使树的最大深度最小化的选择”—— 他们对树的最大深度设置了硬性限制( length-limited, also called minimum variance Huffman coding ):

• “无论是否存在平局，构建一棵最大深度最多为 16 步的树，因此最大码字长度为 16 位”(如 Huffman codes used in JPEG image compression 中) (Jpeg huffman coding procedure)

• “无论是否存在平局，构建一棵最大深度最多为 15 步的树，因此最大码字长度为 15 位”(如 Huffman codes used in DEFLATE 和 Huffman codes used in gzip

• “无论是否存在平局，构建一棵最大深度最多为12步的树，因此最大码字长度为12位”( "Huff0 uses a 12-bit limit." )

我的理解是人们开发了几个heuristic algorithms for limiting Huffman codeword lengths工作正常，但是 heuristics don't always give exactly the best possible compression .

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

• 劳伦斯·L·拉莫尔 (Lawrence L. Larmore) 和丹尼尔·S·赫希伯格 (Daniel S. Hirschberg)。 "A Fast Algorithm for Optimal Length-Limited Huffman Codes"
• "Optimal Length-Limited Huffman Codes"
• "A fast algorithm for optimal length-limited Huffman codes"