algorithm - 构建霍夫曼树时如何选择优先级？

Question

假设我的字符及其频率如下：

Char    Freq.
 a       1
 b       2
 c       3
 d       4
 e       5
 f       6
 g       7
 h       8

在构建树时，在第 2 步中，我们有：

   [3]     [3]   [4]   [5]   [6]   [7]   [8]
   / \      c     d     e     f     g     h
  /   \
[1]   [2]
 a     b

现在，既然我们有两个 3，我们如何确定它们的优先级呢？

在霍夫曼编码中，这被认为是：

[3]    [3]     [4]   [5]   [6]   [7]   [8]
 c     / \      d     e     f     g     h   
      /   \
    [1]   [2]
     a     b

为什么？

score 1 · Accepted Answer

有什么不同？暂时忽略，d在h第一种情况下，你会得到

a = 00
b = 01
c = 1

在第二种情况下，

a = 10
b = 11
c = 0

只要c在最终树中处于相同高度，其代码将具有相同的长度。

score 0 · Accepted Answer

你的情况并不有趣。将 0 和 1 分配给分支是任意的，因此您概述的选择会导致相同的代码，即相同的代码长度，无论哪种方式。

然而，在一些有趣的情况下，您需要选择三个或更多具有相同总频率和不同形状的组。任何选择都将导致相同的整体最优性，即在提供的频率上对提供的符号进行编码的总比特数完全相同。然而，这些选择可能会导致具有不同位长组合的不同形状树。然后可以做出这样的选择以到达更深或更浅的树，这取决于所需的内容。

score 0 · Accepted Answer

我会优先考虑 c （更短的代码）。这将符合霍夫曼树的基本原则：优先级/更短的代码用于即时结果，而更低的优先级用于更多的解析。