string - 在文本中查找字典字符串的最快方法

Question

我有一个文本文件和字典。该词典由一个恰好 8 个字符长的单词列表组成。我浏览文本文件并每 8 个字符搜索一次字典(“滑动窗口”)。

目前，我使用python字典数据结构作为查找表。它的摊销查找时间为 0(1)，但我想知道是否存在使用问题的特定性质/结构的更快的算法/数据结构。

Answer 1

您可以尝试 aho-corasick 多模式匹配器。它构建了一个有限状态机，使用 trie 和广度优先搜索最长前缀的第一次出现，该前缀也是字典字符串的后缀。您可以在 https://phpahocorasick.codeplex.com 尝试我在 php 中的实现。 .它还增强了搜索通配符的算法。