如何根据规则排序并解决循环引用中的重复项？

Question

为了更清楚地说明我的问题，我先来讲讲我遇到的实际情况。

我正在制作一个物理面板，上面有很多字，可以选择性地点亮，以便组成句子。我的情况是这样的：

1. 我知道我想展示的所有句子。
2. 我想找出一个最短的、有顺序的单词集合，这样我就能展示所有的句子。

举个例子：

 SENTENCES:
 "A dog is on the table"
 "A cat is on the table"
 SOLUTIONS:
 "A dog cat is on the table"
 "A cat dog is on the table"

我尝试用“位置规则”来解决这个问题，找出在所有句子中每个独特单词的左右应该放哪些单词。在上面的例子中，“on”这个词的规则是“左边有(A, dog, cat, is) + 右边有(the, table)”。

这种方法在简单的情况下有效，但我实际遇到的情况有两个额外的困难，让我卡住了，这两个困难都与重复单词有关：

1. 句内重复：比如“the cat is on the table”中有两个“the”。
2. 循环引用：在三个句子“一个红色的猫” + “我的猫在桌子上” + “那张桌子是红色的”中，规则会说红色应该在猫的左边，猫应该在桌子的左边，而桌子又应该在红色的左边。

所以我的问题是：

有什么算法类别（或者更好的是：具体的算法）可以研究和解决这种问题？你能提供一些参考资料或代码示例吗？

编辑：复杂性水平

从第一轮的回答来看，实际的复杂性水平（即句子之间的差异有多大）是一个重要因素。所以，这里有一些相关信息：

1. 我大约有1500个句子想要表示。
2. 所有句子基本上都是对大约10个句子的修改，只有少数几个单词会变化。举个例子，我的句子可能都是在讲“某个宠物相对于家具的位置”或“某个家具的物理描述”。
3. 用来构建所有句子的独特单词数量少于100个。
4. 句子最多8个单词长。

在这个项目中，我使用的是Python，但任何可读性合理的语言（例如：不是混淆的Perl！）都可以。

谢谢你提前花时间来帮忙！

Answer 1

我是一名生物信息学家，这个问题听起来可以通过对所有句子进行全局的多序列比对来解决。具体来说，就是对比的时候不允许有任何不匹配（也就是说，完全不允许有不同的地方），同时允许有一些空格（也就是可以有空格，但希望空格少一些），然后再找出没有空格的共同序列。

如果这个方法和你的问题是一样的，那就意味着你的问题确实是NP完全的，因为多序列比对是NP完全的，虽然有很多启发式算法可以在合理的时间内运行。不过，遗憾的是，大多数多序列比对的算法是为了处理DNA或蛋白质序列中的字符，而不是处理英语单词。

例子

这里有一个我描述的比对示例，使用的是提问者给出的三句话。我不知道我给出的比对是否是最优的，但这是一种可能的解决方案。空格用一系列的短横线表示。

Sentence 1: ---- -- A red cat -- -- --- ----- -- ---
Sentence 2: ---- My - --- cat is on the table -- ---
Sentence 3: That -- - --- --- -- -- --- table is red
Consensus:  That My A red cat is on the table is red

这个方法的一个优点是，除了能给你完整的单词序列外，还能显示哪些单词属于哪些句子。

Answer 2

如果我理解得没错，这个问题可以看作是最短公共超序列的问题。这个问题是NP完全的，但有一些近似算法可以解决。你可以在谷歌上搜索“最短公共超序列算法”，会找到一些相关的论文，包括这篇。

对于两个输入序列，这个问题可以用一个简单的动态规划（DP）算法来解决，但如果是多个序列就不行了，因为每增加一个序列，就需要在DP表中增加一个维度，这样会导致计算量急剧增加。

Answer 3

经过一周的编码（这是一个业余项目），我决定自己回答自己的问题。这并不是因为之前得到的答案不够好，而是因为我结合了三位回答者的意见来编写我想要的解决方案，觉得只给其中一位致谢不太公平，因为我确实参考了他们的建议。

先说结论：我想出的这个方法效果非常不错（至少在我实际使用的案例中是这样）。我有1440个句子，每个句子平均大约6个单词，使用了70个独特的单词。这个程序运行大约需要1分钟，最后给我提供了一个仅有76个单词的超序列（比问题的“物理”下限多了10%）。

这个方法是专门为我的实际情况量身定做的，特别是因为大部分句子都是围绕大约10个“原型”构建的（可以参考我在问题中编辑的第2点），整个过程分为四个步骤：

1. 同构缩减
2. 相似性缩减
3. 粗略冗余优化
4. 精细冗余优化

同构缩减

我把两个句子A和B称为“同构”，如果把A变成B和把B变成A所需的步骤完全相同。举个例子：

'A dog is on the carpet'
'A cat is under the table'

这个转换总是需要将第一个字符串中位置1、3、5的单词替换为第二个字符串中位置1、3、5的单词。

将句子分组为“同构家族”可以轻松创建优化后的超字符串，只需在共同的根句中 "A __ is __ the __" 插入位置1、3、5的变量元素列表。

相似性缩减

在这个阶段，句子的数量大幅减少（通常会有大约50个来自同构家族的超序列和一些孤立句子，这些孤立句子与池中的其他句子没有同构关系）。程序分析这个新池，并将两个最相似的字符串合并在一起，然后对合并后的新集合和尚未合并的字符串重复这个过程，直到所有内容都合并成一个超序列。

粗略冗余优化

在这个阶段，我们已经有了一个有效的超序列，能够覆盖所有原始的1440个句子，但这个超序列的效果并不好，因为很多词重复了。这个优化步骤通过使用超序列来构造所有句子，然后从中删除所有未被使用的词，来去除大部分冗余词。

精细冗余优化

前面的优化结果已经相当不错，但有时通过最后一步可以再去掉一两个单词。这个优化通过找到重复出现的单词，检查是否可以将两个连续的重复词移动到超序列中的同一位置，同时仍然能够构造所有句子。举个例子：给定超序列

aaa xxx bbb ccc ddd eee xxx fff

程序会尝试将两个 xxx 单词向彼此靠拢：

aaa bbb xxx ccc ddd eee xxx fff
aaa bbb xxx ccc ddd xxx eee fff
aaa bbb ccc xxx ddd xxx eee fff

如果超序列变成：

aaa bbb ccc xxx xxx ddd eee fff

并且没有句子同时使用两个 xxx，那么其中一个 xxx 就可以去掉。

当然，这个步骤可以通过一次移动多个位置来优化（想想希尔排序和冒泡排序的区别），但程序的整体结构就是这样，速度提升也不大，所以我选择了这个“优化程度较低”的方法，因为这个“移动过程”在其他地方也会用到。

再次感谢所有最初的回答者：你们的建议对我想出这个解决方案至关重要。欢迎你们对这个解决方案的评论！

最后说明：一旦程序完成/项目结束（最多几个月），我会将其发布在GPL下，并在原问题中添加代码库的链接。我相信将问题标记为“收藏”应该会通知标记者任何编辑……当然，如果你对实际代码感兴趣的话！