python - 高效地在海量文件中搜索字符串

Question

我找到了这个想法的变体，但没有一个能让我(对 python 非常陌生)到达我需要去的地方。

场景如下:

1. 我有一个巨大的 27 gig hashfile.txt，由不同行上的唯一字符串组成。
2. 我需要逐行解析此文件，在另一个不太大 (~800mb) addresses.txt 文件中搜索匹配项
3. 找到匹配项后，需要将其写入outfile.txt

我目前的代码已经尽我所能进行了优化，但每秒只能达到 150 行左右。考虑到我的 hashfile.txt 中有超过 15 亿行，任何优化都会有所帮助。

fin = 'hashed.txt'
nonzeros = open('addrOnly.txt', 'r')
fout = open('hits.txt', 'w')
lines = nonzeros.read()
i = 0
count = 0

with open(fin, 'r') as f:
    for privkey in f:
            address = privkey.split(", ")[0]
            if address in lines:
                    fout.write(privkey)
            i = i+1
            if i%100 == 0:
                    count = count + 100
                    print "Passed: " + str(count)

Answer 1

您要实现的可能是 Rabin-Karp string search .当您在某个语料库中同时搜索多个字符串时，它非常高效。

有关 python 实现的更多信息，请参阅本文。 python efficient substring search

由于您一次搜索多个地址，您可能希望对 addresses.txt 中的条目进行散列处理，并在每次迭代时将它们与 Rabin-Karp 散列值同时进行比较。阅读有关 Rabin-Karp 中滚动哈希的更多信息，您将了解其工作原理。

由于 Rabin-Karp 要求所有模式的长度相同；实际上，所有地址的长度都可能是不可忽略的，您可以将它们全部截断为相同(不太短)的长度并使用前缀进行散列。此外，您可能希望将 Rabin-Karp 散列修改为对空白和地址格式化方式的微小差异不变，并且还可以类似地定义一个自定义字符串比较器来确认匹配。