生成编码时永远不会产生字符串“00”的霍夫曼代码

Question

我正在尝试使用霍夫曼编码为一组符号创建最佳编码。然而，对编码施加了约束，使得没有编码包含字符串“00”。
例如，编码“A”=“0”和“B”=“10”将不满足约束，因为字符串“BA”编码为“100”，其中包含“00”子字符串。
这意味着代码字也不能包含字符串“00”。例如，编码“A”=“1”、B=“00”和C=“01”将不满足约束，因为编码“B”总是会导致“00”出现在编码中。

我尝试修改维基百科上找到的霍夫曼编码算法：

1. 为每个符号创建一个叶节点并将其添加到优先级队列中。
2. 当队列中有多个节点时：
   1. 从队列中删除优先级最高（概率最低）的两个节点
      • 如果两个节点都不是叶子节点，则选择优先级最高的节点和优先级最高的叶子节点。这确保了至少一个所选节点是叶节点。
   2. 创建一个新的内部节点，将这两个节点作为子节点，并且概率等于两个节点概率之和。
      • 如果一个节点不是叶节点，则使该节点成为新内部节点的右子节点（编码时使其为“1”）。这可以避免创建“00”子字符串。
   3. 将新节点添加到队列中。
3. 剩下的节点就是根节点，树就完整了。
4. 在所有代码的开头添加“1”，以避免两个相邻符号编码时出现“00”子串。

还有一种情况是队列中只剩下两个节点都是非叶节点。我不知道如何解决这个问题。否则，我相信这会创建一个满足约束的编码，但我不确定它是否是最优的，并且我想确定它是最优的。

Answer 1

我想我应该从代码中的任何“0”后面必须跟有“1”的规则开始。这满足了代码中不允许包含“00”的约束。它还避免了在对两个相邻符号进行编码时产生“00”子串的问题。

生成的代码树如下所示，其中

• 红色阴影区域中的节点是包含“00”的代码
• 包含红色 X 的节点是以“0”结尾的代码
• 绿色节点是可用的有效代码

请注意，由于霍夫曼代码是无前缀代码，因此选择有效代码之一会消除该节点的所有后代。例如，选择使用代码“01”会消除树左侧的所有其他节点。换句话说，选择“01”使“01”成为叶子，并断开“01”下面的两个连接。

另请注意，内部节点的左子节点的代码将比右子节点的代码长，因此概率较低的子节点必须连接在左侧。这当然是必要的。留下它作为练习来证明它是足够的。（如果还不够，那么练习就是提出最佳分配算法。）