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

Question

我正在一个比较大的文本文件里进行搜索，这个文件有10万行，大小是7MB。虽然文本内容不算多，但我需要进行很多次搜索。我想查找一个特定的字符串，并返回它出现的那一行。我的文本文件格式是这样的，目标字符串只会出现在一行里。

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

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

我在一个Google App Engine的应用中使用这段Python代码。

谢谢！

Answer 1

首先，不要直接解码字节。

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。这样运行会快一点，但如果有多个返回值，修改起来会稍微麻烦一些。

Answer 2

如果你一直在重复搜索同一个文本文件，考虑给这个文件建立一个索引。比如，可以创建一个字典，把每个单词和它出现的行数对应起来。虽然建立这个索引会花一些时间，但之后搜索的速度会非常快，几乎是瞬间完成。

如果你在搜索不同的文本文件，或者因为某些原因无法给文件建立索引，那么你可能也找不到比KMP算法更快的方法。

补充一下：我提到的索引只适用于单个单词的搜索，不适合多个单词的搜索。如果你想搜索多个单词（任何字符串），那么可能就无法建立索引了。

Answer 3

1. 一次性把整个文本加载到内存中，不要一个一个行地读取。
2. 在这块文本中搜索你想要的模式。如果找到了，就用 text.count('\n',0,pos) 来获取行号。
3. 如果你不需要行号，可以找出前一个和后一个换行符，把这一行从文本中切出来。

在Python中，循环的速度比较慢，而字符串搜索的速度很快。如果你需要查找多个字符串，可以使用正则表达式。

如果这样还不够快，可以使用外部程序，比如 grep。