哈夫曼树问题

Question

我们刚开始研究 class 中的霍夫曼树，我遇到了一些问题。首先给出数据和频率...

 Data         %    /    -    +     *
 Frequencies  5    10   25   30    50

创建自定义霍夫曼树。

我创造了...

然后用相应的数据替换了频率，但是我的室友得到了不同的答案？是我错了吗？

此外，我似乎无法解决这个问题，

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。

Answer 1

这是我的 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(/)

满足这个要求，尽管编码不同：

我们的树不同的原因是因为我的树是 Canonical Huffman Code，这意味着我只需要列出它们的编码（或路径）的符号和长度，任何人都可以重新构造霍夫曼 codes/tree:

*: 1
+: 2
-: 3
/: 4
%: 4

这是因为 0 总是终止一个代码，而 1 总是意味着至少还有 1 个节点，除了最外面的叶子 (%, 1111)，这是可能的，因为我们知道最大代码长度（树的最大深度）。

Answer 2

您正确应用了霍夫曼算法，您的树没有问题，而且它是唯一可能具有这些频率的树。可能有不同的绘制方法，但所有针对这些频率的正确树都将具有完全相同的拓扑结构。什么在左边或右边并不重要。重要的是每个符号有多少分支。

有 16 种不同的方式将位分配给分支（每个分支 0 可以在左边或右边），所以你可以获得那么多不同的代码。然而它们都是最优的。如果你室友的代码中每个符号的位数相同，那么无论你如何绘制树或如何分配 0 和 1，你们都是对的。

哈夫曼树问题

Huffman Tree Issue

tree

theory

huffman-code

alphabet