4

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

这是场景：

  1. 我有一个巨大的 27 gig，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)
4

2 回答 2

5

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

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

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

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

于 2013-03-14T04:01:32.840 回答
4

对于这样的数据大小，我会使用适当的数据库。数据库针对大型数据集的快速处理进行了优化，比人们可能编写的 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 行示例上它有效:)

于 2013-03-14T05:48:34.213 回答