引言

在上一篇文章中，我们介绍了如何通过递归算法来构建 commafree code 集合。递归算法的缺点是复杂度呈指数上升，导致效率降低。本文将介绍如何通过回溯算法来优化构建 commafree code 集合的方法。

Algorithm C

框架

算法框架分为五步：

  1. 初始化数组
  2. 选择主串
  3. 更新选择的影响
  4. 递归尝试并打印结果
  5. 回溯

初始化

这一步单独提出来是因为除了在上一篇介绍的数据结构，有不下 10 个数组要初始化，他们的作用主要是记录颜色和候选集，以及记录递归信息方便回溯。我尝试用伪代码来描述，但是发现伪代码太冗长了，而且 x, c 这些字母看得头疼，这里我们只关注 MEM 数组，回到上篇最后的例子：alt text 这是当 m=2 时，我们需要初始化的 MEM 数组，而它恰好每行 16 个存下了所有 4 位二进制，第一行记录的是每个 code 的颜色，可以看到 #0000 #0100 #1000 #1010 #1111 已经是红色了，其他 3 个是红色好理解，因为他们属于 abab 的形式，本身就被排除在外，为什么#0100 和#1000 也被涂成红色呢？接着往下看，并且过程中自己尝试解释下，我在最后会揭晓答案。 剩下的辅助数组和变量我们就不展开初始化了，接着进入到下一步。

尝试主串

接下来我们大胆地从候选集中选一个颜色是蓝色的码，选中之后将它变成绿色，假如这次我们选择 #0010，同时记录下这一步的选择，进入下一步。

更新&标记

更新稀疏集合

当我们选了 #0010 后，根据 7 个稀疏集合的定义，我们要可以快速地更新他们，从而继续更新状态数组的颜色。对于 P 集合，我们只要把 #0010 相应的前缀链表“关闭”即可，比如 P1 在 MEM[20-24] 之间记录的是 $0\star \star \star$ 开头的码，那么只要令 MEM[30] 是链表头-1 就行了，也就是 MEM[30]=1f，然后对于 P2，也一样“关闭” $00\star \star$，依此类推 S 集合也是如此处理。

最后来处理 CL 集合，它是记录蓝色词的循环移位集合，这里选了 #0010，那么就要把它所在的位移集合都移除掉，也就是 MEM[140-141] 代表的集合，将 MEM[150]=13f，更新前如下图： before cl 更新后如下图： after cl

状态标记

你也许注意到在更新后的 CL 集合中，还少了 #1001，这又是为什么呢？ 这里要引出又一个数组 poison，当我们选择了 #0010 后，我们将

\[(\star001, 0\star \star \star), (\star \star00,10\star \star), (\star \star \star 0,010\star)\]

放入 poison 数组，对于第一组，因为 $0\star \star \star$ 包含了绿色的 #0010，那么 $\star001$ 必然为红，也就可以把 #1001 变成红，也就解释了为什么上面 CL 也删掉 #1001（另外 6 个集合也要对应删掉 #1001）。换句话说，每一对前缀和后缀必须至少包含一绿一红，同理，第三组因为 $\star \star \star0$ 已经包含绿了，那$010\star$ 都必须是红。对于第二组因为包含全为蓝，无法删除，就先保留。

回溯

当我们走到了尽头发现没有蓝色状态的码时，我们就要开始回溯了，鉴于精妙的数据结构，我们只要完成 更新&标记 的逆操作就好，对于 poison 数组的记录，我们只要把上面单独删除的码加回到各个集合就好，这里特别提一下，因为稀疏集合在删除时只是把待删元素交换到末位没有物理删除，所以添加回来只要简单改一下 TAIL 指针就好。然后对于这次选中的候选码，简单地“打开”集合就好，也是修改 TAIL 指针。

小结

本文详细介绍了可以看到虽然搜索算法不可避免的是指数级的复杂度，但还是能通过巧妙的数据结构和搜索策略来提高效率。

最后回答下初始化那节遗留的问题，为什么 #0001 和 #0010 在初始化时就是红色了， 因为题目定义解法必须包括 #0001 或者 #0010 其中一个，不管选哪个，#0100 和#1000 都和#0001 或者#0010 属于同一个主码，所以被排除。

课后题

最复杂的莫过于书中列出的表格，如果你恰好有书，可以看到关于算法 C 的表格 1 和表格 2，它们分别展示了算法 C 的第 1 步和第 2 步，但实际操作起来我发现了一些有趣的地方，留下几道问题帮助读者更好理解 MEM 的奥妙所在。

  1. 在表格 1 中，可以看到 20 这行分成了两部分，每部分 5 个数，为什么前半部分记录了#0001 #0010 #0011 是递增的，后半部分第一个却是#1100 而不是#1001 呢？
  2. 接上题，你的答案能解释 MEM[5d] 和 MEM[5e] 吗？MEM[bc] 和 MEM[bd] 呢？
  3. 在表格 1 中，最后 3 行 cl 数组的赋值顺序是什么？为什么 MEM[146] 是#1100 而 MEM[147]是#1001 排在后面呢？
  4. 为什么初始化首先排除了#0100 和#1000？（有没有好好听讲）

后记

其实这 3 篇文章只是对 Knuth 的 TAOCP 4B 中 algorithm C 粗浅解读，虽然书里列出了算法的 12345 步，但我并不认为用序号的形式展示一段带分支的代码是个好主意，而直接用伪码反而更加清晰，所以我在叙述时完全抛开了书中繁琐的步骤，而是从更符合代码直觉的角度上介绍了算法的实现。

PS：发现一些书中的错误，在 Ex41 和算法 C 的实现中，Knuth 偶尔会把 MEM 的地址写成 40d，而应该是 4d，不幸的是这中错误已经被人指出来了，如果想拿到 Knuth 签名的 San Serriffe 银行支票还是要趁早。