高效搜索海量文件中的字符串

Question

我发现了这个想法的变体，但没有一个可以让我（对 python 非常陌生）到达我需要的地方。

这是场景：

1. 我有一个巨大的 27 演出，hashfile.txt由单独的字符串组成。
2. 我需要逐行解析这个文件，在另一个不太大（~800mb）的addresses.txt文件中搜索匹配项
3. 当找到匹配时，这需要写入 outfile.txt

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

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

对于这样的数据大小，我会使用合适的数据库。数据库针对大型数据集的快速处理进行了优化，比人们编写的 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（我将在这里使用它），并创建两个表和一个索引。

$ 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 行示例上它有效:)

Answer 2

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

这篇文章中关于 python 实现的更多信息。python高效的子串搜索

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

由于 Rabin-Karp 要求所有模式的长度相同；在实践中，所有地址可能都有一些不可忽略的长度，您可以将它们全部截断为相同（不要太短）的长度并使用前缀进行散列。此外，您可能希望修改 Rabin-Karp 哈希，使其对空格和地址格式的细微差异保持不变，并且还需要类似地定义一个自定义字符串比较器来确认匹配。