长度受限的霍夫曼码的打包合并算法

也许这只是构建霍夫曼代码的另一种方法。您是否看过http://cbloomrants.blogspot.com/2010/07/07-02-10-length-limitted-huffman-codes.html？ IMO的包合并算法没有建立霍夫曼树。您要查找Golomb代码。     

是的，这只是构建对代码字长度有限制的霍夫曼代码的一种方法。 霍夫曼代码使用可以唯一确定的二进制字符串来编码字母表中的每个字母。例如，如果您的字母是{A，B，C}并且A比B和C更常见，则以下编码可以很好地工作：

A - 0
B - 10
C - 11

诸如0010110之类的编码字符串可以进行唯一编码，因为编码位字符串的长度已经由霍夫曼代码定义（在这里-每个以0开头的字符串的长度为1，每个以1开头的字符串的长度都为2）。因此，字符串解码为0 | 0 | 10 | 11 | 0 = AABCA。 现在，构造霍夫曼代码时的“问题”是如何选择编码位串，以使所得到的编码平均而言尽可能短。在您的问题中，还有一个附加约束，即任何代码字的长度都不能超过L。通常的想法是使用较短的字符串来编码更常见的符号。 打包合并算法的细节并不重要，关键在于您要使用一种算法来选择\“面额总计为n-1 \的最小钱币值的硬币集”。如果您有面额为2-1、2-2，...的硬币，并且想要从中建立100美分的总价值，则可以认为此过程首先具有价值100的硬币，然后拆分它变成两个50美分（2-1），然后继续将硬币分成所需的一半，例如50美分+ 25美分+ 12.5美分+ 12.5美分。这对应于二叉树的构造。每当拆分硬币时，您都将在二叉树中创建一个内部节点，并在更深一层上添加两片叶子。 现在，最小化货币价值的想法是，与“较高频率”符号链接的“硬币”使用起来更昂贵，因此您希望将这些硬币拆分得更少，这与使用较短的代码相对应。 这些细节留给读者练习。