python - 在非索引文本文件中搜索单词的最快方法 - Python

Question

考虑一个 150 万行的文本文件，每行大约 50-100 个单词。

要查找包含单词的行，使用 os.popen('grep -w word infile') 似乎比

for line in infile: 
  if word in line:
    print line

否则如何在 python 中的文本文件中搜索单词？搜索大型未索引文本文件的最快方法是什么？

Answer 1

有几种快速搜索算法(参见 wikipedia )。他们要求您将单词编译成某种结构。 Grep 正在使用 Aho-Corasick algorithm .

我还没有看到 python 的 in 的源代码，但是

1. word 为每一行编译需要时间(我怀疑 in 编译任何东西，显然它可以编译它，缓存结果等)，或者
2. 搜索效率低下。考虑在“wordword”中搜索“word”，您首先检查“worw”并失败，然后检查“o”，然后“r”并失败，等等。但是没有理由重新检查“o”或“r”，如果你很聪明。例如，Knuth–Morris–Pratt algorithm根据搜索到的词创建一个表，告诉它发生失败时可以跳过多少个字符。