我有一个文本文件和字典。该字典由一系列长度为8个字符的单词组成。我遍历文本文件并在每8个字符（“滑动窗口”）中搜索字典。
目前，我使用Python字典数据结构作为查找表。它具有平摊查找时间为0（1），但我想知道是否存在更快的算法/数据结构，可以利用问题的特定性质/结构。
目前，我使用Python字典数据结构作为查找表。它具有平摊查找时间为0（1），但我想知道是否存在更快的算法/数据结构，可以利用问题的特定性质/结构。
在文本中查找字典字符串的最快方法
4
- Roy
10
1“Words” 的意思是实际的单词，它们由空格和标点符号分隔，还是仅仅指字符序列，就像基因编码一样？ - tobias_k
1@tobias_k 那就是Aho-Corasick算法所做的大致工作。 :) - biziclop
@tobias_k：我指的是字符序列。 - Roy
字典固定而文本文件改变吗？还是反过来？ - biziclop
1@Roy 对于一个固定的字典，Aho-Corasick 算法可能是最好的算法，因为你可以预先构建用于匹配的有限状态机，然后将其重复使用于所有搜索中。 - biziclop
显示剩余5条评论
2个回答
1
你可以尝试使用Aho-Corasick多模式匹配。它使用Trie构建有限状态机，并广度优先搜索最长前缀，该前缀也是字典字符串的后缀的第一次出现。你可以在https://phpahocorasick.codeplex.com中尝试我的PHP实现。它还增强了算法以搜索通配符。
- Micromega
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接