9

为了更清楚地解释我的问题，我将从解释我面临的现实案例开始。

我正在构建一个物理面板，上面有很多单词，可以选择性地点亮，以组成句子。这是我的情况：

  1. 我知道我想显示的所有句子
  2. 我想找出[one of] 最短的一组 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 cat is on the table”有两个“the”。
  2. 循环引用：在“一只红猫”+“我的猫在桌子上”+“那张桌子是红色的”三个句子中，规则规定 RED 应该在 CAT 的左侧，CAT 应该在TABLE 和 TABLE 的左侧应位于 RED 的左侧。

因此，我的问题是：

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

编辑：复杂程度

从第一轮答案看来，实际的复杂程度（即一个句子与另一个句子有多大不同）是一个重要因素。所以，这里有一些信息：

  1. 我有大约 1500 个句子要表示。
  2. 所有句子本质上都是对大约 10 个句子的受限池的修改，其中只有几个单词发生了变化。在前面的例子的基础上，这有点像我所有的句子都会谈论“某人的宠物相对于一件家具的位置”或“某人的家具的物理描述”。
  3. 用于构建所有句子的唯一词数<100。
  4. 句子最多8个字。

对于这个项目，我使用的是 python，但任何合理可读的语言（例如：不是混淆的 perl！）都可以。

提前感谢您的宝贵时间！

4

4 回答 4

10

如果我理解正确，这相当于最短的常见超序列问题。这个问题是NP完全的，但存在近似算法。谷歌出现了几篇论文，包括这一篇。

在两个输入序列的情况下，可以使用简单的 DP 算法解决该问题，但这并不能推广到多个序列，因为每个序列本质上都需要您向 DP 表添加一个维度，这会导致指数爆炸。

于 2011-04-26T03:40:46.910 回答
6

我是一名生物信息学家，这听起来可以通过对所有具有无限错配惩罚（即完全禁止错配）和适度空缺惩罚（即允许空缺，但更喜欢更少空缺）的句子进行全局多序列比对来解决，然后读取无间隙共有序列。

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

例子

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

第 1 句：---- -- 一只红猫 -- -- --- ----- -- ---
句子2：----我的----猫在桌子上----
句子 3: 那 -- - --- --- -- -- --- 桌子是红色的
共识：My A red cat is on the table is red

这种方法的一个优点是对齐不仅可以为您提供完整的单词序列，还可以显示哪些单词属于哪些句子。

于 2011-04-26T02:33:21.157 回答
2

我没有实际证据，但如果您的问题不是 NP 完全或 NP 难，我会感到非常惊讶。我可以找到一个保证给出最佳答案的算法。但即使是少量合理长度的句子（例如 16 个句子，每个句子 8 个单词），它也会陷入困境并且无法在任何合理的时间内运行。因此，我建议您不要寻找确切的答案，而是寻找能够提供合理算法的良好启发式方法。

我建议的启发式方法是使用成对的句子，为它们解决http://en.wikipedia.org/wiki/Longest_common_subsequence_problem（Python标准库中的解决方案，查找 difflib），解决随机冲突的部分，并用那个句子替换这对。对你所有的句子都这样做，你会有一个好的解决方案。不是一个伟大的，但一个好的。

如果你想变得聪明，你可以寻找增量改进，多次运行，试着聪明地了解如何随机解决这些差异，等等。但简单的方法可能会给出相当好的答案，而不需要太多的努力。

于 2011-04-26T02:13:07.097 回答
1

经过一周的编码（这是一个爱好项目），我决定回答我自己的问题。这不是因为我之前得到的答案不够好，而是因为我使用它们中的三个来编写我想要的解决方案，并且只将功劳归功于其中一个响应者感觉不对，因为我确实使用了输入由他们三人想出一个满意的解决方案。

让我们从头开始：我提出的启发式给出了非常令人满意的结果（至少对于我使用它的现实案例）。我有 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多个位置来优化（想想shell 排序与冒泡排序），但程序的一般结构是这样的，而且速度上的增益很小，我更喜欢这个“不太优化”的过程，因为这个“转移过程”也在其他地方使用。

再次感谢所有最初的响应者：您的输入对于让我想到这个解决方案至关重要。您对此解决方案的评论也非常受欢迎！

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

于 2011-05-04T00:28:05.713 回答