前缀代码是一组代码，因此没有代码是另一个代码的前缀。例如，以下集合是前缀代码：
10
11
000
001
0100
0101
0110
0111
与n = 8会员。我认为这些通常是用某种类型的霍夫曼树创建的。
我的问题是：你能帮我创建一个函数来生成一个包含“n”个成员的二进制前缀代码吗？
像这样的东西：
list<int> GenerateBinaryPrefixCodes(int n);
此外，在比特的总和最小化的意义上，要求是“最优的”。
我更喜欢 C/C++/C#/类似的答案。这不是真正的家庭作业，但我这样标记它，因为听起来这将是一个很好的硬件问题。
谢谢！
前缀代码
正如您所指出的，前缀代码是给定代码不是任何其他给定代码的前缀的代码。这是一个非常笼统的定义。霍夫曼编码是前缀码的一种受限形式。
霍夫曼编码的一个常见用法是最小化（优化）编码“消息”所需的总比特数。“消息”通常是符号序列，通过将每个符号出现映射到特定前缀代码并在其位置写出前缀代码来对其进行编码。可以使用任何一组前缀代码来执行此操作。但是，霍夫曼编码将根据比特数产生最短的消息。
例如，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
在此过程结束时，单个“引用”列表项将成为 Huffman 树的根。您可以通过对树进行深度优先遍历来枚举前缀代码。为每个左分支写一个“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 bits * 4) = 8 bits。请注意，对于平衡树，所有前缀代码最终都具有相同的位数。
树位权重只是所有叶子的路径长度的总和。您可以通过最小化总路径长度来最小化位权重 - 这是通过平衡树来完成的。
如您所见，最小化任何给定的前缀树没有太大价值，您最终会得到一个固定长度的符号编码。当您考虑生成的编码消息的位权重时，该值就出现了。最小化导致霍夫曼编码。
有多少种不同的编码？
前缀代码可以通过遍历二叉树并为随后的每个较低分支发出“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。
将比特数之和最小化的要求等价于要求代码是每个符号出现一次的字符串的最佳霍夫曼码。因此，只需创建一个具有n 个唯一字符的字符串并为其生成 Huffman 树。该算法在 Wikipedia 上进行了概述。
您的 n=8 示例似乎并不代表最佳解决方案。
10 11 000 001 0100 0101 0110 0111 总位数：26
000 001 010 011 100 101 110 111 总位数：24
当频率恒定时，最佳前缀编码将是固定长度。每个前缀代码的长度为 log(n)，并且是从 0..n-1 开始的字母表的二进制表示。
编辑n 不是 2 的幂的情况。
// generate tree
function PCode(n) {
var a = [];
for(var x=1; x<=n; x++) {
a.push({"v":x});
}
for(var x=0; x<n-1; x++) {
var node = {"v": null, "l": a.shift(), "r": a.shift()};
a.push(node);
}
return a.pop();
}
//print
function Print(node, s) {
if(node["v"] != null) {
console.log(s);
}
if(node["l"] != null) Print(node["l"], s + "0");
if(node["r"] != null) Print(node["r"], s + "1");
return;
}
//test
Print(PCode(3), "");
请看一下这个 C++ 教程网站。它将为您提供有用的 C++ 结构。我在右侧的“相关”部分看到其他类似的 SO 问题可能会有所帮助。
我以前用 C 语言用递归算法做过这个，是的，这将是一个很好的家庭作业问题。
生成问题（解码的唯一性）可以通过构建n个叶子节点的二叉树来保证，并枚举每个这样的节点在树中的位置（0是左分支，1是右分支）。你是对的，霍夫曼树有这个属性。请注意，对于霍夫曼树，每个节点的权重等于其代表字符的频率，并且树是使用递归属性构建的，即节点连接的左右决策基于到该点的子节点的总和. 这种累积和属性也是为什么斐波那契分布为霍夫曼树提供最坏情况压缩的原因。
请注意，霍夫曼编码最适合固定字母的可变编码。非固定字母表的一个示例是决定将“ the ”视为要压缩的集合中的单个元素（而不是两个空格和一个字母）。
您的问题似乎与替换无关。您只需要 n 个元素的前缀代码，其中所有前缀代码的长度总和最小化。这与构建每个元素频率为 1 的 Huffman 树相同（因为它保证了总编码字符串的最小编码，对您而言，它等于每个编码元素的比特之和恰好一次，即最小化总数位）。注意：这保证了最小的编码，它不保证最快的实现。您可能不需要为每个方法调用构建树。不幸的是，我不知道有什么实现。
让我们用二进制表示为 1x 的数字对二进制字符串 x 进行编码。否则，0 和 00 将映射到同一个 int。
std::vector<int> GenerateBinaryPrefixCodes(int n) {
std::vector<int> list;
for (int i = n; i != 2 * n; ++i) list.push_back(i);
return list;
}