大型文本文件中最快的文本搜索方法

Question

我正在对一个相当大的txt文件进行文本搜索（100k行，7mo）。 文本并不是非常大，但我需要进行很多搜索。 我想查找目标字符串并返回它出现的行。 我的文本文件格式化得只能在一行中出现目标。

什么是最有效的方法？我要进行很多搜索，所以我想提高速度。 这是我现在的代码：

def lookup_line(target):
    #returns line of the target, or None if doesnt exist
    line=None
    dir=os.path.dirname(__file__)
    path=dir+'/file.txt'
    file=open(path,'r')
    while line==None:
        l=file.readline()
        l=unicode(l,'utf-8')
        if target in l:
            break
        if l=='': break #happens at end of file, then stop loop
    line=l
    if line=='':line=None #end of file, nothing has been found
    file.close()
    return line

我使用这段Python代码来开发Google App Engine应用程序。

谢谢！

- user375348

---

你正在寻找单词、短语或者有奇怪标点符号的文本（比如编译器错误）吗？在搜索之间，文件是否会发生变化？ - sje397

我正在搜索非拉丁字符的单词。 这是由于文件格式的原因，我需要这两个空格和方括号以确保单词在行中的正确位置被找到。 - user375348

Answer 1

1. 一次性将整个文本加载到RAM中，不要逐行读取。
2. 在块中搜索模式。如果找到它，请使用text.count('\n',0,pos) 获取行号。
3. 如果您不需要行号，请查找前一个和下一个EOL以从文本中剪切该行。

在Python中循环速度较慢。字符串搜索非常快。如果您需要查找多个字符串，请使用正则表达式。

如果这还不够快，请使用像grep这样的外部程序。

- Aaron Digulla

---

为什么不使用Solr来完成这项工作，而不是用Python？您可以简单地连接Solr功能并在Python中使用结果。 - Prometheus

Answer 2

如果您一遍又一遍地搜索相同的文本文件，请考虑对该文件进行索引。例如，创建一个将每个单词映射到其所在行的字典。这将需要一些时间来创建，但将使搜索变为O(1)。

如果您正在搜索不同的文本文件，或者由于某些原因无法对文件进行索引，则可能无法比KMP算法更快。

编辑：我描述的索引仅适用于单词搜索，而不是多词搜索。如果要搜索多个单词（任何字符串），则可能无法对其进行索引。

- Niki Yoshiuchi

---

好的建议，您可以编写一个算法，从单词索引中进行多词搜索。多词索引很可能是浪费时间的。此外，您可以将单词边界的字符存储为索引。使用正则表达式可以使这成为一项微不足道的任务。 - marr75

好的观点。至少很容易确定一行是否包含句子中的所有单词。然而，我认为对单词部分进行搜索（例如“uick brown fo”）将无法以有意义的方式进行索引。 - Niki Yoshiuchi

Answer 3

首先，不要显式解码字节。

from io import open

其次，考虑这样的事情。

with open(path,'r',encoding='UTF-8') as src:
    found= None
    for line in src:
        if len(line) == 0: break #happens at end of file, then stop loop
        if target in line:
            found= line
            break
    return found

这段代码可以稍微简化一下，使用return None或者return line代替break。这样可以微微提高运行效率，但是当有多个返回值时修改会稍微麻烦一些。

- S.Lott

Answer 4

您想要搜索速度达到10GB/s吗？ https://www.codeproject.com/Articles/5282980/Fastest-Fulltext-Vector-Scalar-Exact-Searcher

什么是最有效的方法？

如果有向量，则最有效的方法是使用向量；如果没有，则使用最快的SCALAR memmem()函数。正好上面的文章展示了它们的实际操作，如果您需要遍历大型文本文件，则 memmem() 变体 Railgun_NyoTengu() 是一种开源公共领域的方式。

- Georgi

---

@Steve 当然，我只是想让SO的观众们拥有最新的答案/链接。很快就会编辑好... - Georgi