使用python在大文本文件中搜索字符串的快速方法

Question

这是我目前的情况:

• 我有一个2.5MB的文本文件,大约250k字符串,按字母顺序排序
• 每个字符串都是唯一的
• 我不需要修改文本文件中的条目:加载文本文件后,永远不会编辑它
• 文本文件在开始时加载,然后我只需要通过它搜索字符串

最后一点是问题所在.实际上我需要搜索完全匹配和字符串的部分匹配.我写的算法只涉及使用正则表达式结合一些尝试来使进程更快:例如,我将字典的索引硬编码到我的脚本中,识别字母表的单数字母,然后拆分大文本文件fictionary成26个较小的字典.这完全没用,脚本仍然非常慢.在这里略读一些帖子,我确信尝试了mmap:但是在给定正则表达式的情况下找到所有部分匹配看起来毫无用处.最后我得出结论,特里可以解决我的问题,虽然我几乎不知道这是什么.我应该尝试一下吗？如果是这样,我应该如何继续在python中创建一个trie？marisa-trie模块好吗？感谢大家

编辑:通过"部分匹配",我的意思是我有一个字符串的前缀.我不需要在结尾或中间的比赛,只是在开始时.

Answer 1

最简单快捷的解决方案:

#!/usr/bin/env python

d = {}

# open your file here, i'm using /etc/hosts as an example...
f = open("/etc/hosts","r")
for line in f:
    line = line.rstrip()
    l = len(line)+1
    for i in xrange(1,l):
        d[line[:i]] = True
f.close()


while True:
    w = raw_input('> ')
    if not w:
        break

    if w in d:
        print "match found", w

这里稍微复杂一点,但内存效率高:

#!/usr/bin/env python

d = []

def binary_search(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        midval = a[mid]
        if midval < x:
            lo = mid+1
        elif midval > x:
            hi = mid
        else:
            return mid
    return -1


f = open("/etc/hosts","r")
for line in f:
    line=line.rstrip()
    l = len(line)+1
    for i in xrange(1,l):
        x = hash(line[:i])
        d.append(x)
f.close()

d.sort()

while True:
    w = raw_input('> ')
    if not w:
        break

    if binary_search(d, hash(w)) != -1:
        print "match found", w