在大型字符串文件中查找部分字符串匹配的最有效方法(python)

Question

我下载了维基百科文章标题文件,其中包含每篇维基百科文章的名称.我需要搜索可能匹配的所有文章标题.例如,我可能有"曲棍球"这个词,但我想要的维基百科的曲棍球文章是"Ice_hockey".它也应该是一个不区分大小写的搜索.

我正在使用Python,有没有一种比逐行搜索更有效的方法？我会在理想情况下每分钟执行500次或1000次此搜索.如果逐行是我唯一的选择,我可以做一些优化吗？

我认为文件中有几百万行.

有任何想法吗？

谢谢.

Answer 1

如果您想匹配单个单词，格雷格的答案很好。如果你想匹配子字符串，你需要一些更复杂的东西，比如后缀树（http://en.wikipedia.org/wiki/Suffix_tree）。一旦构建完成，后缀树就可以有效地回答对任意子字符串的查询，因此在您的示例中，当有人搜索“hock”时，它可以匹配“Ice_Hockey”。