1

高水平

我正在尝试折叠句子列表中的常见子字符串，并仅显示它们不同的区域。所以采取这个：

Please don't kick any of the cats
Please do kick any of the cats
Please don't kick any of the dogs
Please do kick any of the dogs
Please don't kick any of the garden snakes
Please do pet any of the garden snakes

并返回：

Please [don't|do] [kick|pet] any of the [cats|dogs|garden snakes]

更多细节

  • 我一直在研究最长的公共子串算法，但这似乎只比较两个字符串。
  • 我只对比较字符串中的整个单词感兴趣。
  • 只想从左到右评估字符串。
  • 不常见子串的长度不会是相同的词数（“猫”与“花园蛇”）

我正在寻求有关算法的帮助。我相信这是 LCS 问题的变体，我认为是对后缀树的某种处理。可以解释和实现的伪代码将是理想的。

另一个例子

Please join thirteen of your friends at the Midnight Bash this Friday
Don't forget to join your friend John at the Midnight Bash tomorrow
Don't forget to join your friends John and Julie at the Midnight Bash tonight

变成：

[Please|Don't forget to]
join
[thirteen of your friends|your friend John|your friends John and Julie]
at the Midnight Bash
[this Friday|tomorrow|tonight]

也许这种方法

这种方法怎么样...

for an array of sentences
  loop with the remaining sentence
    find the "first common substring (FCS)"
    split the sentences on the FCS
    every unique phrase before the FCS is part of the set of uncommon phrases
    trim the sentence by the first uncommon phrase
  end loop
4

2 回答 2

0

将每个唯一单词映射到单个对象。然后构建一个条件概率表（参见马尔可夫链）来枚举单词跟随每个序列的次数。

于 2014-01-24T03:18:12.943 回答
-1

有趣的是，我很久以前就一直在考虑创造像你这样的东西，直到我意识到这实际上是一种人工智能。需要考虑的因素太多：语法、句法、情况、错误等。但如果您的输入总是如此固定，例如“请 [A1|A2|..] [B1|B2|..] 任何 [C1 |C2|..]"，那么也许一个简单的正则表达式模式就可以了："^Please\s*(?(don't|do))\s*(?\w+)+\s*any of the\s *(?.)*$"。

于 2014-01-24T01:50:41.767 回答