4

私はこのアイデアの変種を見つけましたが、私が必要な場所に（Pythonに非常に慣れていない）私を導くことができるものはありませんでした。

シナリオは次のとおりです。

  1. 私は1つの巨大な27ギグを持っており、hashfile.txtすべてが別々の行にあるユニークなストリングで構成されています。
  2. このファイルを1行ずつ解析して、別のそれほど大きくない（〜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 (ここではそれを使用します) を使用して、2 つのテーブルと 1 つのインデックスを作成します。

$ 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ステートメントです。インデックスは、ほとんどのアドレス テーブルと同様に、(できれば) ずっと RAM にあります。hashfileaddress

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 に答える