在大文件中高效地搜索字符串

Question

我发现了类似的想法，但没有一个能让我（对Python非常新手）到达我需要的地方。

以下是场景：

1. 我有一个巨大的、27GB的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)

- dannyincolor

---

你现在的代码是什么？这些文件看起来像什么？ - Blender

特别是，您能描述一下您目前的算法吗？ - davidg

可能这将是一个I/O绑定的问题（尽管这取决于算法的选择），因此在这种情况下使用的特定语言不太可能产生很大影响。 - davidg

@tor 这是一个极端的概括。请记住，许多字符串函数，例如str.find()在C中实现（在CPython中），非常快速。我编写的一个Python工具的模拟实现，在我使用-O3编译之前，实际上比我的C实现快约10%。 - Jonathon Reinhart

查找时不要使用列表，应该使用时间复杂度为O（1）的数据结构，例如字典。可以使用以下代码创建一个字典：lines = dict.fromkeys(nonzeros.read().split("\n"), 1)。请注意，也不要使用大字符串进行查找。 - sberry

Answer 1

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

有关Python实现的更多信息，请参见此文章。 python高效子字符串搜索 由于您一次要搜索多个地址，因此您可能希望对addresses.txt中的条目进行哈希处理，并将它们与Rabin-Karp哈希一起比较，每次迭代都要进行比较。阅读更多关于Rabin-Karp中滚动哈希的内容，您就会了解这是如何工作的。

由于Rabin-Karp要求所有模式具有相同的长度； 在实践中，所有地址可能都具有某些非常重要的长度，您可以将它们全部截断到相同的（不要太短）长度并使用前缀进行哈希。此外，您可能希望修改Rabin-Karp哈希以不变地处理空格和地址格式的小差异，并定义一个类似的自定义字符串比较器来确认匹配。

- Andrew Mao

---

我怀疑27GB的搜索字符串，即使经过哈希处理，也不太可能放入内存中。 - davidg

@davidg 根据原帖，addresses.txt 文件大小为800MB。 - Jonathon Reinhart

@sberry提出了一个很好的短期解决方案，让我可以去睡觉，但这是一种深入的答案，将带领我学习许多新东西 - 谢谢！ - dannyincolor

嗯，只要最短地址的长度不太短，就应该可以工作。 - Voo

比较短字符串并不是问题，而是长字符串会导致速度变慢。我会将其截断到一定长度，然后直接比较非常短的地址。 - Andrew Mao

Answer 2

由于数据大小如此巨大，建议使用真正的数据库。与可能编写的Python程序相比，数据库更加优化，可以更快地处理大型数据集。

直接字符串比较是昂贵的。让我们对字符串进行哈希处理，以便哈希的完整二进制树索引有很好的机会适合内存。md5为128位，并且计算非常快。

首先，计算每个记录的md5值并将其存储在另一个文本文件中：

from hashlib import md5
with open('hashfile.txt') as input:
  with open('hashfile-md5.txt', 'w') as output:
    for line in input:
      value = line.rstrip() # cut '\n'
      output.write(value)
      output.write('\t') # let our file be tab-separated
      output.write(int(value).hexdigest(), 16)) # md5 as long number
      output.write('\n')

对于address.txt，同样的操作，生成address-md5.txt。

选择Postgresql、mysql或SQLite（这里我会使用SQLite），创建两个表和一个索引。

$ sqlite3 matching-db.sqlite

create table hashfile (
  txt varchar(64), -- adjust size to line lengths of hashfile.txt
  hash number(38) -- enough to contain 128-bit hash
);

create table address (
  txt varchar(64), -- adjust size to line lengths of address.txt
  hash number(38) -- enough to contain 128-bit hash
);

现在加载我们的数据。与通过 dbapi 从 Python 插入的方式相比，本地数据库导入通常更快。

.separator \t
.import hashfile-md5.txt hashfile
.import address-md5.txt address

现在我们可以创建一个索引：

create index x_address_hash on address(hash);

这是一个 select 语句，可以高效地扫描大型的 hashfile 表格，并从小型的 address 表格中查找匹配的哈希值。索引将始终在 RAM 中（希望如此），大部分地址表也将在内存中。

select h.txt
from hashfile h, address a
where h.hash = a.hash and h.txt = a.txt;

这个想法是利用索引x_address_hash来高效匹配哈希值，如果哈希值相同，则比较实际文本值。

我没有在29 MB的数据上尝试过，但在一个玩具2行示例上它是有效的 :)

- 9000

---

这个问题我已经问了好多年了，但你的回答非常详细且精彩。感谢你抽出时间撰写此回答；我正在重温我最初遇到的那个问题，并计划使用某种关系型数据库来实现它。 - dannyincolor