带无"00"子串约束的最优霍夫曼编码构建方案咨询

核心约束转化 #

先把需求转化为树的构造规则，更易落地：

1. 单个码字不能含"00" → 树中任意根到叶子的路径，不能出现连续两个0；
2. 拼接后不能含"00" → 若一个码字以0结尾，下一个码字的开头不能是0。结合前缀码特性，只要保证所有以0结尾的码字都是叶子节点，且内部节点的左子节点只能是叶子，就能同时满足两个约束。

修改后的最优编码算法 #

步骤1：初始化优先队列 #

将每个符号作为叶子节点，节点权重设为对应概率，优先队列按权重从小到大排序（每次取概率最低的节点）。

步骤2：迭代合并节点 #

当队列节点数 > 1时：

• 取出权重最小的两个节点n1、n2；
• 合并规则：
  1. 若其中一个是内部节点，且它的左子节点非叶子 → 把该内部节点设为新节点的右子节点（对应编码位1），另一个节点设为左子节点（对应编码位0）；
  2. 若两个都是内部节点：
     • 队列中还有叶子节点的话，放弃其中一个内部节点，改取权重最小的叶子节点与当前内部节点合并；
     • 队列只剩这两个内部节点时，给权重较大的那个内部节点添加一个虚拟叶子节点（权重为0，不对应任何符号），将虚拟节点作为左子节点、该内部节点作为右子节点合并成新节点，再将新节点与另一个内部节点正常合并。
• 创建新内部节点，权重为合并节点的权重之和，按规则设置子节点后放回队列。

步骤3：生成码字 #

从根节点遍历到每个叶子节点：左子节点记0，右子节点记1。生成的码字自动满足"无00"约束，无需额外加前缀。

针对"仅剩两个非叶子节点"的处理 #

当队列只剩两个非叶子节点时，所有原始符号已合并到这两个节点中：

1. 检查两个节点的子树：如果其中一个节点的左子节点都是叶子，直接将其作为新节点的左子节点，另一个作为右子节点；
2. 如果两个节点的左子节点都有非叶子节点，给权重较大的节点加一个权重为0的虚拟叶子节点，先合并虚拟节点与该内部节点，再用新生成的节点和另一个内部节点合并。虚拟节点不影响编码平均长度，因为权重为0。

正确性与最优性验证 #

1. 约束满足：通过树的构造规则，所有码字本身无00；同时因为前缀码特性，若0是一个码字，其他码字都不能以0开头，拼接时不会出现0后跟0的情况；
2. 最优性：合并逻辑遵循霍夫曼编码的核心——每次合并权重最小的节点，仅在约束限制时调整，虚拟节点不影响平均长度计算，因此是满足约束的最优前缀码。

内容的提问来源于stack exchange，提问作者1um0