小编1um*_*um0的帖子

我正在尝试使用霍夫曼编码为一组符号创建最佳编码。然而，对编码施加了约束，使得没有编码包含字符串“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”子串。

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