从较小的字符串中的一大组字符串中查找所有匹配项

Question

我有大量的单词和短语（词典或词典），其中包含通配符。我需要在一个较小的字符串（目前约150个字符）中找到这些单词和短语的所有实例。

最初，我想反向运行该操作；这是要检查我的较小字符串中的每个单词是否在Lexicon中存在，可以将其实现为哈希表。问题在于我的词典中的某些值不是单个单词，而很多是通配符（例如substri *）。

我正在考虑使用Rabin-Karp算法，但是我不确定这是最佳选择。

什么是执行此操作的有效算法或方法？

样本数据：

该词典包含数百个单词，并且可能会扩展。这些词可能以通配符（星号）结尾。以下是一些随机示例：

• 好
• 坏
• 已释放*
• 粗心*
• 巨大的损失

我们正在分析的文本（此时）是简短的，非正式的（语法上的）英语陈述。文本的主要示例（同样是在此时）是Twitter Tweet。这些限制为大约140个字符。例如：

Just got the Google nexus without a contract. Hands down its the best phone 
I've ever had and the only thing that could've followed my N900.

注意我们正在对本文进行非常简单的情感分析可能会有所帮助；我们的情绪分析技术与我无关。我只是将现有解决方案迁移到“实时”处理系统，并且需要执行一些优化。

Answer 1

我认为这是Aho-Corasick字符串匹配算法的绝佳用例，该算法专门用于在单个字符串中查找大字符串集的所有匹配项。它分两个阶段运行：第一阶段创建匹配的自动机（可以预先完成，只需要线性时间），第二阶段使用自动机来查找所有匹配项（只需要线性时间） ，再加上与比赛总数成正比的时间）。该算法也可以适用于支持通配符搜索。

希望这可以帮助！