在多个字符串中测试多个子字符串的算法

Question

我有几百万个字符串X，每个字符串大概有不到20个单词。我还有一个包含几千个候选子字符串C的列表。对于X中的每一个字符串x，我想检查一下C中是否有任何字符串包含在x里面。目前我使用的是一个简单的双重循环，但已经过了一段时间，还是没有完成……有没有什么好的建议？我在用Python，如果有人知道有什么好的实现方法，那就太好了，不过任何语言或通用算法的链接也很不错。

相关问题：

• 使用后缀数组和LCP快速查找文本中的子串
• 在Python中使用grep搜索文件
• 合并两个非常大的文本文件，逐行更新，且不使用内存
• Python 高效检查大字符串是否包含子串的方法
• 获取单词的上下文
• 在大文本中计数字符串
• Python还是Java用于文本处理（文本挖掘、信息检索、自然语言处理）
• Python: 最佳字典实现

Answer 1

你可以看看这个链接：http://en.wikipedia.org/wiki/Aho-Corasick。它介绍了一种可以快速匹配一组固定字符串的方法，这个方法的速度和所有字符串的总长度成正比。也就是说，先把这些字符串准备好，然后在文本中搜索，所需的时间和文本的长度加上找到的匹配次数成正比。

还有一种快速的精确模式匹配方法是http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm。

Answer 2

这会花费很长时间。你需要把几百万个字符串都跟几千个候选子字符串进行比较，这意味着你要进行几百万乘以几千的字符串比较。是的，这会耗费不少时间。

如果你只是偶尔需要做这个，我建议你使用 fgrep。但如果你经常需要这样做，那就应该考虑实现像 Aho-Corasick 字符串匹配 这样的算法。

Answer 3

把你的一组字符串用一种叫做字典树的结构来编码（我建议用比较大的那一组）。这样查找的速度应该比不太完美的哈希表快，而且还能节省一些内存。