use*_*566 5 language-agnostic algorithm huffman-code
甲前缀代码是一组代码,使得没有代码的另一代码前缀.例如,以下集合是前缀代码:
10
11
000
001
0100
0101
0110
0111
有n = 8会员.我认为这些通常是用某种类型的霍夫曼树创造的.
我的问题是:你能帮助我创建一个能够生成带'n'成员的二进制前缀代码的函数吗？
像这样的东西:
list<int> GenerateBinaryPrefixCodes(int n);
而且,要求是在总位数最小化的意义上它是"最佳的".
我更喜欢用C/C++/C#/类似的答案.这不是真正的功课,但我标记它是因为它听起来像是一个很好的hw问题.
谢谢!
前缀代码
正如您所指出的，前缀代码是给定代码不是任何其他给定代码的前缀的代码。这是一个非常笼统的定义。霍夫曼编码是前缀码的一种受限形式。
霍夫曼编码的一个常见用法是最小化（优化）编码“消息”所需的总位数。“消息”通常是一个符号序列，通过将每个符号出现映射到特定前缀代码并在其位置写出前缀代码来对其进行编码。可以使用任何一组前缀代码来做到这一点。但是，霍夫曼编码将导致基于比特数的最短消息。
例如，可以将 ASCII 字符集视为符号到一组 8 位前缀代码的映射。这甚至可以被认为是霍夫曼编码，前提是编码的消息包含的每个可能符号的数量完全相同。
当要编码的消息包含不相等的符号频率时，有趣的事情就开始了。此时可以通过使用不同长度的前缀码来减少消息的总比特长度。对更频繁的符号使用短前缀代码，对不太频繁的符号使用更长的前缀代码。
从您的示例中，有 8 个要编码的符号。映射到前缀代码“11”和“10”的符号将是消息中最常见的符号。同样，映射到“0111”、“0110”、“1010”和“0100”的符号将是最不常见的。频率越高，前缀码越短。
创建霍夫曼编码的“技巧”是构建一组前缀代码，以便在将消息中的每个符号映射到它们相关的前缀代码之后，消息包含尽可能少的位。
我发现将前缀代码视为一个二叉树很有用，其中每个叶节点都映射到一个符号。例如，与您问题中给出的前缀代码（01、11、000、001、0100、0101、0110、0111）对应的二叉树将是：
+-- (11)
+--+
| +-- (10)
|
| +-- (0111)
--+ +--+
| | +-- (0110)
| +--+
| | | +-- (0101)
| | +--+
+--+ +-- (0100)
|
| +-- (001)
+--+
+-- (000)
要获得括号中的值，您只需在跟随顶部边缘时分配“1”，如果跟随底部边缘则分配“0”。
如何建造这样一棵树？
从表示二叉树和列表的数据结构开始。
二叉树将包含两种类型的节点。1) 代表符号及其频率的叶节点和 2) 代表其下方所有节点累积频率的内部节点（它还需要两个指针，一个用于左分支，一个用于右分支）。
该列表包含来自二叉树的一组有序节点。列表中的节点根据它们指向的节点的频率值进行排序。频率最低的节点出现在列表的前面，并在列表的末尾增加。指向树节点的指针链表可能是一个有用的实现——但任何有序的列表结构都可以。
下面的算法使用两个列表：“参考”和“工作”列表。当从“参考”列表处理节点时，新节点被创建并插入到“工作”列表中，使得“工作”列表保持按节点频率排序。
使用这些数据结构和以下算法来创建霍夫曼编码。
0. Initialize the "reference" list by creating a leaf node for each symbol
then add it into this list such that nodes with the lowest frequency
occur at the front of the list and those with the highest frequency
occur at the back (basically a priority queue).
1. Initialize the "working" list to empty.
2. Repeat until "reference" list contains 1 node
2.1 Set MaxFrequency to the sum of the first 2 node frequencies
2.1 Repeat until "reference" list is empty
If ("reference" list contains 1 node) OR
(sum of the next two nodes frequency > MaxFrequency)
Move remaining nodes to the "working" list
Set "reference" list to empty
Else
Create a new internal node
Connect the first "reference" node to the left child
Connect the second "reference" node to the right child
Set the new node frequency to the sum of the frequencies of the children
Insert the new node into the "working" list
Remove the first and second nodes from the "reference" list
2.2 Copy the "working" list to the "reference" list
2.3 Set the "working" list to empty
在此过程结束时，单个“引用”列表项将成为霍夫曼树的根。您可以通过对树进行深度优先遍历来枚举前缀代码。为每个左分支写一个“0”，为每个右分支写一个“1”。当遇到叶子时，代码就完成了。叶子上的符号由刚刚生成的霍夫曼码编码。
什么是最佳编码
一个可以执行的有趣计算是计算前缀编码的“位权重”。比特权重是表示前缀代码集所需的比特总数。
看看上面的原始树。这棵树的权重是 (2 bits * 2) + (4 bits * 5) + (3 bits * 2) = 30 bits。您使用 30 位来表示 8 个前缀值。您可以使用的最少位数是多少？想想看，当一棵树变得不平衡时，通往某些叶子的路径长度会变长——这会增加重量。例如，4 值前缀树的最坏情况是：
+-- (1 bit)
--+
| +-- (2 bits)
+--+
| +-- (3 bits)
+--+
+-- (3 bits)
总权重为 (1 bit * 1) + (2 bits * 1) + (3 bits * 2) = 9 bits
平衡树：
+-- (2 bits)
+--+
| +-- (2 bits)
--+
| +-- (2 bits)
+--+
+-- (2 bits)
总权重为（2 位 * 4）= 8 位。请注意，对于平衡树，所有前缀代码最终都具有相同的位数。
树位权重只是到所有叶子的路径长度的总和。您可以通过最小化总路径长度来最小化位权重 - 这是通过平衡树来完成的。
如您所见，最小化任何给定的前缀树并没有多大价值，您只会得到固定长度的符号编码。当您考虑生成的编码消息的位权重时，就会出现该值。最小化导致霍夫曼编码。
有多少种不同的编码？
前缀代码可以通过遍历二叉树并为后面的每个较低分支发出“0”并且为后面的每个较高分支发出“1”直到遇到叶子来生成。如：
+--+ (1)
|
--+
| +-- (01)
+--+
+-- (00)
或者，我们可以“翻转”该规则，并为每个较低的分支分配一个“1”，为较高的分支分配一个“0”：
+-- (0)
|
--+
| +-- (10)
+--+
+-- (11)
它们生成两组不同的前缀代码。可以通过对分支进行所有可能的 1/0 分配然后遍历树来生成附加集。这会给你 2^n 套。但是如果你这样做，你会发现可能会生成相同的前缀代码，但顺序不同。例如，前面的树将产生以下集合：{(0, 10, 11), (0, 11, 01), (1, 01, 00), (1, 00, 01)}。然后将树翻转为：
+-- (??)
+--+
| +-- (??)
--+
|
+-- (?)
然后你得到：{(11, 10, 0), (10, 11, 0), (01, 00, 1), (00, 01, 1)}。将它们放在一起为 2^3 = 8 组。但是，如果您想要不考虑顺序的唯一集合，则只有 2 个集合：{(0, 10, 11), (1, 00, 01)}。对平衡树进行相同的练习，并且只有一组。这一切让我相信唯一编码的数量与用于生成前缀代码的树的平衡结构有关。不幸的是，我没有一个确切的公式或计算出来。凭直觉，我猜这个数字是 2^（不同代码长度的数量 - 1）。对于平衡树，即： 2^(1 - 1) = 1; 对于具有两个不同代码长度的树（如上例所示）：2^(2 - 1) = 2；对于您的示例：2^(3 - 1) = 4。