algorithm - 对于三元霍夫曼问题，我们可以为 "4"个字符制作一棵树(或编码方案)吗？

Question

对于三元霍夫曼问题，我们可以为“4”个字符制作一棵树(或编码方案)吗？假设我有 4 个具有这些频率的字符:频率(a)=5 频率(b)=3 频率(c)=2 频率(d)=2

我如何以 0,1,2 的形式对它们进行编码，使得没有代码字是另一个代码字的前缀？

Answer 1

生成最佳三元霍夫曼码的标准算法(如 rici 所提到的)首先包括确保符号数量为奇数——如有必要，添加一个虚拟符号(频率为 0)。

在这种情况下，我们从偶数个符号开始，因此我们需要添加我称之为 Z 的虚拟符号:频率(a)=5 频率(b)=3 频率(c)=2 频率(d)=2 频率(Z)=0。

然后如 Photon 所述，我们将频率最低的 3 个节点重复组合为 1 个组合符号。每次我们用 1 个节点替换 3 个节点时，我们将节点总数减少 2，因此节点总数在每一步都保持奇数。在最后一步(如果我们添加了正确数量的虚拟符号)，我们将把 3 个最终节点组合成一个根节点。

         abcdZ:12
         /  |  \
       2/  1|  0\
    cdZ:4  b:3  a:5
    / | \
  2/ 1| 0\
Z:0  d:2  c:2

所以在这种情况下，一种最佳(霍夫曼)三元编码是:

a: 0
b: 1
c: 20
d: 21
Z: 22 (should never occur).

见 https://en.wikipedia.org/wiki/Huffman_coding#n-ary_Huffman_coding了解更多详情。