这是我目前的情况:
- 我有一个 2.5MB 的文本文件，其中包含大约 250k 个字符串，按字母顺序排序
- 每个字符串都是唯一的
- 我不需要修改文本文件中的条目:文本文件一旦加载，就永远不会被编辑
- 文本文件在开始时加载，然后我只需要通过它搜索字符串
最后一点就是问题所在。实际上我需要搜索字符串的完全匹配和部分匹配。我编写的算法只涉及正则表达式的使用，并结合一些尝试使过程更快:例如，我将字典的索引硬编码到我的脚本中，以识别字母表中的单个字母，然后拆分大文本文件虚构成26本小字典。 那完全没用，脚本仍然非常慢。 浏览了这里的一些帖子，我确信可以尝试 mmap: 但在给定正则表达式的情况下，找到所有部分匹配项看起来毫无用处。 最终我得出结论，trie 可以解决我的问题，虽然我几乎不知道这是什么。我应该尝试一下吗？如果是这样，我应该如何继续在 python 中创建一个特里树？ Is marisa-trie module good?感谢大家
编辑:通过“部分匹配”，我的意思是我有一个字符串的前缀。我不需要在结尾或中间进行匹配，只需要在开头。
请您参考如下方法:
最简单和最快的解决方案:
#!/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
