如何根据规则进行排序,但重复项目以解决循环引用？

Question

为了更清楚地解释我的问题,我将首先解释我面临的现实案例.

我正在构建一个物理面板,上面有许多单词,可以有选择地点亮,以便编写句子.这是我的情况:

1. 我知道我想要显示的所有句子
2. 我想找出[最短的]一组ORDERED单词,这些单词允许我显示所有句子

例:

 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"单词的规则集将是"left(A,dog,cat,is)+ right(the,table)".

这种方法适用于琐碎的案例,但我的现实情况还有两个困难让我陷入困境,这与重复单词的需要有关:

1. 句子重复:"猫在桌子上"有两个"the".
2. 循环引用:在一组三句话中"一只红猫"+"我的猫在桌子上"+"那张桌子是红色的",规则会说明RED应该在CAT的左边,CAT应该在TABLE和TABLE的左边应该在RED的左边.

我的问题是:

研究和解决这类问题的算法类别(甚至更好:具体的算法是什么)是什么？你能发布一些参考或代码示例吗？

编辑:复杂程度

从第一轮答案看,实际的复杂程度(即一个句子与另一个句子的差异程度)是一个重要因素.所以,这里有一些信息:

1. 我想要代表约1500个句子.
2. 所有句子基本上都是对约10个句子的限制池的修改,其中只有少数几个词发生变化.在前面的例子的基础上,它有点像我的所有句子都会谈到"某人的宠物相对于一件家具的位置"或"某人家具的物理描述".
3. 用于构建所有句子的唯一单词的数量<100.
4. 句子最多8个字.

对于这个项目,我使用的是python,但任何合理可读的语言(例如:not notfuscated perl!)都没问题.

提前谢谢您的时间!

Answer 1

如果我理解正确,这相当于最短的常见超序问题.这个问题是NP完全的,但存在近似算法.谷歌发表了一些论文,包括这篇论文.

在两个输入序列的情况下,可以通过简单的DP算法解决该问题,但是这不会推广到多个序列,因为每个序列基本上要求您向DP表添加维度,这导致指数爆炸.

Answer 2

我是一名生物信息学家,听起来这可以通过对所有句子进行全局多序列比对来解决,这些句子具有无限的不匹配惩罚(即完全不允许不匹配)和适度的差距惩罚(即允许间隙,但更喜欢更少的间隙),然后读掉无间隙的共识序列.

如果这个公式等同于你的问题,那么这意味着你的问题确实是NP完全的,因为多个序列比对是NP完全的,尽管有许多启发式算法在合理的时间内运行.不幸的是,大多数MSA算法被设计用于处理DNA或蛋白质序列的特征,而不是英语单词.

例

这是我描述的一种对齐方式的示例,使用OP给出的三个句子的集合.我不知道我给出的对齐是否是最佳的,但它是一种可能的解决方案.间隙用一系列破折号表示.

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 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可以去。

当然，最后一段可以通过xxx一次移动多个位置来优化（想想希尔排序与冒泡排序），但程序的总体结构是这样的，并且速度的增益如此之小，我更喜欢这种“不太优化”的程序，因为这种“转移程序”也在其他地方使用。

再次，非常感谢所有最初的回复者：您的意见对于让我想到这个解决方案至关重要。也非常欢迎您对此解决方案提出意见！

最后注意：一旦程序完成/项目完成（最坏的情况是几个月），我将在 GPL 下发布它，并在原始问题中添加代码存储库的链接。我相信将问题标记为“最喜欢”应该通知标记者任何编辑......当然，以防万一您对实际代码感兴趣！