哈夫曼树问题
Huffman Tree Issue
我们刚开始研究 class 中的霍夫曼树，我遇到了一些问题。首先给出数据和频率...
Data % / - + *
Frequencies 5 10 25 30 50
创建自定义霍夫曼树。
我创造了...
120
/ \
50 70
/ \
30 40
/ \
15 25
/ \
5 10
然后用相应的数据替换了频率，但是我的室友得到了不同的答案？是我错了吗？
此外，我似乎无法解决这个问题，
What would the Huffman code look like if all symbols in the alphabet had
equal frequency?
非常感谢任何帮助！
P.S。这些只是学习指导问题，与作业无关。
编辑：我是如何得出答案的：
在树的底部取 5 和 10，将它们相加得到一个 "ghost" 节点 15。添加 25 到右侧，因为它更大，然后通过将它们加在一起创建了一个幽灵节点 40。将30放在40的左边，因为它比较小，然后将两者相加创建了一个ghost节点70。最后将 50 添加到 70 的左侧，因为它较小，然后将两者相加创建最终的幽灵节点 120。
这是我的 Huffman.pm 提出的：
0 -- *
10 -- +
110 -- -
1110 -- /
1111 -- %
以上是编码输入字符串的最短符号。
它是一棵树，有一个隐含的根：
Root
/ \
0(*) 1
/ \
0(+) 1
/ \
0(-) 1
/ \
0(/) 1(%)
编码方式有多种，但必须保持一致。
根据 wikipedia:
the bit string representing some particular symbol is never a prefix of the bit string representing any other symbol
你的树
120
/ \
50(*) 70
/ \
30(+) 40
/ \
15 25(-)
/ \
5(%) 10(/)
满足这个要求，尽管编码不同：
0 *
10 +
1100 %
1101 /
111 -
我们的树不同的原因是因为我的树是 Canonical Huffman Code，这意味着我只需要列出它们的编码（或路径）的符号和长度，任何人都可以重新构造霍夫曼 codes/tree:
*: 1
+: 2
-: 3
/: 4
%: 4
这是因为 0 总是终止一个代码，而 1 总是意味着至少还有 1 个节点，除了最外面的叶子 (%, 1111)，这是可能的，因为我们知道最大代码长度（树的最大深度）。
您正确应用了霍夫曼算法，您的树没有问题，而且它是唯一可能具有这些频率的树。可能有不同的绘制方法，但所有针对这些频率的正确树都将具有完全相同的拓扑结构。什么在左边或右边并不重要。重要的是每个符号有多少分支。
有 16 种不同的方式将位分配给分支（每个分支 0 可以在左边或右边），所以你可以获得那么多不同的代码。然而它们都是最优的。如果你室友的代码中每个符号的位数相同，那么无论你如何绘制树或如何分配 0 和 1，你们都是对的。
我们刚开始研究 class 中的霍夫曼树，我遇到了一些问题。首先给出数据和频率...
Data % / - + *
Frequencies 5 10 25 30 50
创建自定义霍夫曼树。
我创造了...
120
/ \
50 70
/ \
30 40
/ \
15 25
/ \
5 10
然后用相应的数据替换了频率，但是我的室友得到了不同的答案？是我错了吗？
此外，我似乎无法解决这个问题，
What would the Huffman code look like if all symbols in the alphabet had
equal frequency?
非常感谢任何帮助！
P.S。这些只是学习指导问题，与作业无关。
编辑：我是如何得出答案的：
在树的底部取 5 和 10，将它们相加得到一个 "ghost" 节点 15。添加 25 到右侧，因为它更大，然后通过将它们加在一起创建了一个幽灵节点 40。将30放在40的左边，因为它比较小，然后将两者相加创建了一个ghost节点70。最后将 50 添加到 70 的左侧，因为它较小，然后将两者相加创建最终的幽灵节点 120。
这是我的 Huffman.pm 提出的：
0 -- *
10 -- +
110 -- -
1110 -- /
1111 -- %
以上是编码输入字符串的最短符号。 它是一棵树，有一个隐含的根：
Root
/ \
0(*) 1
/ \
0(+) 1
/ \
0(-) 1
/ \
0(/) 1(%)
编码方式有多种，但必须保持一致。 根据 wikipedia:
the bit string representing some particular symbol is never a prefix of the bit string representing any other symbol
你的树
120
/ \
50(*) 70
/ \
30(+) 40
/ \
15 25(-)
/ \
5(%) 10(/)
满足这个要求，尽管编码不同：
0 *
10 +
1100 %
1101 /
111 -
我们的树不同的原因是因为我的树是 Canonical Huffman Code，这意味着我只需要列出它们的编码（或路径）的符号和长度，任何人都可以重新构造霍夫曼 codes/tree:
*: 1
+: 2
-: 3
/: 4
%: 4
这是因为 0 总是终止一个代码，而 1 总是意味着至少还有 1 个节点，除了最外面的叶子 (%, 1111)，这是可能的，因为我们知道最大代码长度（树的最大深度）。
您正确应用了霍夫曼算法，您的树没有问题，而且它是唯一可能具有这些频率的树。可能有不同的绘制方法，但所有针对这些频率的正确树都将具有完全相同的拓扑结构。什么在左边或右边并不重要。重要的是每个符号有多少分支。
有 16 种不同的方式将位分配给分支（每个分支 0 可以在左边或右边），所以你可以获得那么多不同的代码。然而它们都是最优的。如果你室友的代码中每个符号的位数相同，那么无论你如何绘制树或如何分配 0 和 1，你们都是对的。