Pythonの順序不変ハッシュ

Question

Pythonでは、ファイルの行の順序不変のハッシュを、そのコンテンツを「一意に」識別する手段として、すぐに計算したいと思います。これらのファイルは、例えば、select ... from tableの出力であり、従って、線の順序はランダムである。

ここでは、（hashlibのハッシャーの1つを使用して）必要なものを実現する例を示しますが、行をソートする必要はありません。 行をソートすることは、目的を達成する、つまりファイル内の行の順序に依存しないハッシュを取得することに過ぎないことに注意してください。しかし、明らかに、私はO（n * log（n））コストを避けたいと考えています。ファイルがはるかに長い場合。

def get_hexdigest(filename, hasher, blocksize=65536, order_invariant=False): 
    if not os.path.isfile(filename): 
     return None 
    if order_invariant: 
     with open(filename, 'r') as f: 
      for line in sorted(f): 
       hasher.update(line.encode()) 
    else: 
     with open(filename, 'rb') as f: 
      while True: 
       buf = f.read(blocksize) 
       hasher.update(buf) 
       if len(buf) < blocksize: 
        break 
    return hasher.hexdigest() 

、50K行は1メガバイトのファイル：

%%time 
get_hexdigest('some_file', hashlib.sha1()) 
# Wall time: 1.71 ms 

しかし：

%%time 
get_hexdigest('some_file', hashlib.sha1(), order_invariant=True) 
# Wall time: 77.4 ms 

をそれを行うには良い/より高速な方法は何ですか？

in this answerと同じように、ScalaはMurmurhashに基づく順序不変のハッシュを持っていますが、私はそれが32ビットバージョンのmmh3（私の使い方では衝突が起こりやすいと思います） CやCythonで何かを実装するのではなく、Pythonで利用できます。 Murmurhash3は128ビットバージョンですが、その出力はx64とx86では異なります。私はマシンに依存しない結果を得たいと思っています。

ので、要約すると、私が希望：良好な分散と

• マシンアーキテクチャ
• 低衝突率全体で一貫性のある結果、すなわち、少なくとも128ビットを（私がするハッシュを必要はありません。暗号化）
• 合理的に高速です。つまり、1MB、50Kラインファイルの場合、少なくとも5ms未満です。
• PyPiまたはCondaのライブラリとして、可能であれば容易に利用できます。
• 繰り返し行のファイルに従うことができます（つまり、行ごとのハッシュをXORするのは非スターターです。同一の行のペアは互いに打ち消し合います）。

---

編集やメモ：いくつかのコメントへの おかげで、上記のコードは、メモリ内の行をソートするために更新されます。 order_invariant is Trueの元のバージョンであった：

with os.popen('sort {}'.format(filename)) as f: 
     for line in f: 
      hasher.update(line.encode(encoding='utf-8')) 
    return hasher.hexdigest() 

（上記使用されるファイルのために）関連する壁時間は、その後238ミリ秒でした。これは77ミリ秒に短縮されましたが、ラインをソートしないよりも遅くなりました。並べ替えはn行分のn * log（n）コストを追加します。

（UTF-8への）エンコード（UTF-8への）とモードの読み込み'r'と'rb'は、行を読み込むときに必要です。私は、ファイルにASCIIデータだけが含まれていると仮定することに頼りたくはありません。 'rb'で読み取ると、正しく分割されない行につながる可能性があります。 order_invariantがFalseのときは同じ懸念がありません。なぜなら、ファイルを分割する必要がないため、最も高速な方法は、バイナリデータのチャンクをスラップして、ハッシャを更新することです。

Answer 1

実際に問題が発生した場合は、ファイルをソートするか（select ... from table order by ...）別の解決策が必要です。

とにかく、使用してPythonで可能なアプローチfrozenset：

#!/usr/bin/python 

lines1 = ['line1', 'line2', 'line3', 'line4'] 
lines2 = ['line2', 'line1', 'line3', 'line4'] # same as lines1 but different order 
lines3 = ['line1', 'line1', 'line3', 'line4', 'line5'] 


for lines in [lines1, lines2, lines3]: 
    print(lines) 
    print(hash(frozenset(lines))) 
    print('') 

出力

['line1', 'line2', 'line3', 'line4'] 
8013284786872469720 

['line2', 'line1', 'line3', 'line4'] 
8013284786872469720 

['line1', 'line1', 'line3', 'line4', 'line5'] 
7430298023231386903 

私はそれはあなたのパフォーマンスが制約と一致しないだろう。私はfrozenset（）の時間複雑さ（Big O）を知らない。 また、行が一意であると仮定します。もう一度、根本的な問題に別の方法で対処することを強くお勧めします。

Answer 2

これまでに興味深いコメントや回答をいただき、ありがとうございます。

この時点では、大容量ファイル（> 350K行）の最適な答えは、（a）です。これはMurmurhash3に基づいており、各行にmmh3.hash128()を追加しています。小さいファイルの場合は（b）です。これは128ビットのハッシュを生成するように調整されたthe frozenset approach proposed by Rolfの変形です（これらの128ビットの品質を保証しませんが）。私の設定で

ライン毎A）mmh3.hash128()と追加

import mmh3 
def get_digest_mmh3_128_add(filename): 
    a = 0 
    with open(filename, 'rb') as f: 
     for line in f: 
      a += mmh3.hash128(line) 
    return '{:032x}'.format(a & 0xffffffffffffffffffffffffffffffff) 

：万行あたり定数0.4秒。私の設定で

B）は、2つのfrozensetのハッシュ

def get_digest_hash_frozenset128(filename): 
    with open(filename, 'rb') as f: 
     frz = frozenset(f.readlines()) 
    return '{:032x}'.format(((hash(frz) << 64) + hash(frz.union('not a line'))) & 0xffffffffffffffffffffffffffffffff) 

：万行あたり0.2と0.6秒の間です。

ノート

1. は検討した後、私は彼らが潜在的にUTF-8のテキストが含まれている場合でも、バイナリモードでファイルの行を読んでOKだったことを決めました。その理由は、一部のUnicode文字に'\n'が含まれていると、その点でその行が誤って分割されるためです。ファイルは、別の場所と同じダイジェストを取得します。その行の2つの部分が別々に配置されていても（または別の場所に置かれていても）、その確率は非常に遅く、それ。

2. （a）のすべての128ビットハッシュを追加するには、Pythonの任意精度のintを使用します。最初は、128ビットで合計を保持しようとしました（反復して、0xfff...fff定数で）。しかし、Pythonに任意の精度を使用させ、最後にマスキングを行うよりも遅くなることが判明しました。

3. 私はfrozensetの通常のハッシュから、2つのハッシュを取ります：frozensetのものと、frozensetのものから、ハッシュのために異なる種を使用するのと同じ、私は推測する）。

コンプリート結果

フルノートがhere可能です。任意のサイズの擬似ランダムファイルを作成し、それぞれの時間を測定しながらいくつかのダイジェスト手法を試みます。これは、EC2インスタンス（r3.4xlarge、擬似ランダムファイルの格納にEBSボリュームを使用）とJupyter iPythonノートブック、およびPython 3.6で実行されます。 46341行のために

、我々は

fun        lines millis 
get_digest_xxh64_order_sensitive 46341 0.4 * 
get_digest_sha1     46341 1.7 * 
get_digest_hash_frozenset64  46341 8.7 
get_digest_hash_frozenset128  46341 10.8 
get_digest_sha1_by_lines   46341 14.1 * 
get_digest_mmh3_128_add_cy  46341 18.6 
get_digest_mmh3_128_add   46341 19.7 
get_digest_sha1_sort_binary  46341 44.3 
get_digest_sha1_sort    46341 65.9 

*を取得する：これらは、比較のためにちょうどここに、順序に依存しています。

get_digest_hash_frozenset64は、64ビットしか与えないので、実際には適していません。

get_digest_mmh3_128_add_cyは、（a）で与えられた関数のcython化されたバージョンですが、ほとんど違いはありません。

get_digest_xxh64_order_sensitiveは非常に高速ですが、順序に依存します。注文不変のバージョンを得るための私の試み（ここには記載されていません）は、すべてかなり遅い結果をもたらしました。なぜなら、その理由は、ハッシュを初期化してファイナライズするためのコストが高いことが明らかです。

大きなファイルの場合は、get_digest_mmh3_128_add_cyが優勝します。ここで11.8Mラインのためである：

2つのリード候補（オーダー不変ではなく、他の人）を中心に

fun         lines millis 
get_digest_xxh64_order_sensitive 11863283  97.8 * 
get_digest_sha1     11863283  429.3 * 
get_digest_sha1_by_lines   11863283 3453.0 * 
get_digest_mmh3_128_add_cy  11863283 4692.8 
get_digest_mmh3_128_add   11863283 4956.6 
get_digest_hash_frozenset64  11863283 6418.2 
get_digest_hash_frozenset128  11863283 7663.6 
get_digest_sha1_sort_binary  11863283 27851.3 
get_digest_sha1_sort    11863283 34806.4 

、ここで彼らはサイズの関数（行数）に取るどのくらいの時間です。 y軸はマイクロ秒/行で、x軸はファイルの行数です。 get_digest_mmh3_128_add_cyが1行に一定の時間（0.4us）を費やすことに注意してください。

次は長いったらしい答えて申し訳ありません

を繰り返します。これは暫定的な答えです。Murmurhash3の直接実装のnumbaまたはCython（またはC++）の後のさらなる実験を試してみてください。

Answer 3

このメルクルスタイルのソリューションがうまくいかない理由はありますか？

import hashlib 

def hasher(data): 
    hasher = hashlib.sha1() 
    hasher.update(data.encode('utf-8')) 
    return hasher.hexdigest() 


def get_digest_by_line(filename, line_invariant=False, hasher=hasher): 
    with open(filename, 'r') as f: 
     hashes = (hasher(line) for line in f) 
     if line_invariant: 
      hashes = sorted(hashes) 
     return hasher(''.join(hashes))