字符串匹配算法：(多令牌字符串)

Question

我有一本字典，里面有大量的字符串。每个字符串的范围可以是1到4个记号(单词)。例子：

字典：

1. 肖申克救赎
2. 教父
3. 纸浆小说
4. 黑暗骑士
5. 搏击俱乐部

现在我有了一个段落，我需要计算出段中有多少字符串是字典的一部分。例如，当以下段落：

“肖申克救赎”( The Shawshank Redemption )被认为是根据IMDB 250制作的最伟大的电影。至少在我偶尔会在IMDB 250上登陆的一两年里，肖申克救赎一直在与“教父”()争夺榜首。

如果与字典相悖，我应该把那些粗体作为字典的一部分。

我怎么能用最少的字典调用来做这件事。

谢谢

Answer 1

使用特瑞可能会更好。Trie更适合于查找可能要查找的部分匹配(例如，搜索段落的文本)，而不是对字典进行大量调用，这些调用大多会失败。

我认为Trie (或某些变体)之所以合适，是因为它是为了完成您想要做的事情而构建的：

​

​

如果在存储和检索方面使用这个(或者在每个节点使用标记化的单词而不是字母)，这将是存储和检索方面效率最高的(至少据我所知)；存储是因为在每个在标题中包含该单词的Dict条目中存储了几千次单词(就像电影标题中的情况一样)，它将被存储在根下的一个节点中。下一个单词"Shawshank“将位于子节点中，然后”救赎“将出现在下一个节点中，总共有3个查找；然后您将移到下一个短语。如果失败，即短语仅为“Shawshank Looper"，那么在相同的3次查找之后失败，然后移到失败的单词Looper (碰巧，它也是根下的子节点)，就会被击中。这个解决方案在没有mashup电影名称的情况下起作用。

使用哈希表，您将不得不拆分所有单词，检查第一个单词，然后在没有匹配的情况下，继续添加单词并检查该短语是否在字典中，直到您成功，或者到达段落的末尾。所以，如果你点击一个没有电影标题的段落，你就会有和段落中的单词一样多的查找。

Answer 2

这不是一个完整的答案，更像是一个延伸的评论。

在文献中它被称为“多模式匹配问题”。由于您提到模式集有数百万个元素，基于Trie的解决方案很可能执行得很糟糕。

据我所知，在实践中，传统的字符串搜索与许多启发式方法一起使用。DNA搜索、抗病毒检测等都需要快速可靠的模式匹配，因此需要大量的研究工作。

我可以想象如何使用具有滚动哈希函数和一些过滤器(Bloom filter)的Rabin来加快进程。例如，您可以先过滤(例如使用弱散列)，然后实际验证，从而减少所需的验证数，而不是实际匹配子字符串。此外，这将减少使用原始字典本身所做的工作，因为您将存储它的散列或其他过滤器。

Answer 3

在Python中：

import re

movies={1:'The Shawshank Redemption', 2:'The Godfather', 3:'Pretty Woman', 4:'Pulp Fiction'}

text = 'The Shawshank Redemption considered the greatest movie ever made according to the IMDB Top 250.For at least the year or two that I have occasionally been checking in on the IMDB Top 250 The Shawshank Redemption has been battling The Godfather for the top spot.'

repl_str ='(?P<title>' + '|'.join(['(?:%s)' %movie for movie in movies.values()]) + ')'

result = re.sub(repl_str, '<b>\g<title></b>',text)

基本上，它包括从dict值中形成一个大的替换指令字符串。我不知道regex和sub在你给他们的替换指令的大小上是否有限制。你也许要检查一下。

赖