Pythonの最新の高性能ブルームフィルター？
https://stackoverflow.com/questions/311202
-
10-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
かなり多数のアイテム（0.01％の誤検出率を持つ100Mから1Bのアイテムなど）を処理するためのPythonでのプロダクション品質ブルームフィルターの実装を探しています。
Pybloom は1つのオプションですが、DeprecationWarningエラーがスローされるとその年齢を示しているようです。 Python 2.5を定期的に。 Joe Gregorioには、実装もあります。
要件は、高速な検索パフォーマンスと安定性です。また、特に優れたc / c ++実装、または優れたJava実装がある場合はJythonに対してもPythonインターフェイスを作成できます。
それがない場合、〜16E9ビットを処理できるビット配列/ビットベクトル表現に関する推奨事項
解決 3
やがて pybloomfiltermap が見つかりました。私はそれを使用していませんが、それは法案に合うように見えます。
他のヒント
私も最近この道を行きました。私のアプリケーションは少し違っていたように聞こえますが。多数の文字列の集合演算を近似することに興味がありました。
高速ビットベクトルが必要であるという重要な観察を行います。ブルームフィルターに何を入れたいかに応じて、使用するハッシュアルゴリズムの速度についても考慮する必要があります。このライブラリが役立つ場合があります。また、キーを1回だけハッシュする、以下で使用する乱数技術をいじくり回すこともできます。
非Javaビット配列の実装に関して：
- Boostには dynamic_bitset があります
- Javaには BitSet が組み込まれています
BitVector を使用してブルームフィルターを作成しました。ライブラリのプロファイリングと最適化に時間を費やし、パッチをAviに提供しました。そのBitVectorリンクに移動し、v1.5の確認にスクロールダウンして詳細を確認します。最終的に、パフォーマンスはこのプロジェクトの目標ではないことに気づき、それを使用しないことに決めました。
ここに私がうろついていたコードがあります。私はこれをpython-bloomのgoogleコードに載せることができます。提案を歓迎します。
from BitVector import BitVector
from random import Random
# get hashes from http://www.partow.net/programming/hashfunctions/index.html
from hashes import RSHash, JSHash, PJWHash, ELFHash, DJBHash
#
# ryan.a.cox@gmail.com / www.asciiarmor.com
#
# copyright (c) 2008, ryan cox
# all rights reserved
# BSD license: http://www.opensource.org/licenses/bsd-license.php
#
class BloomFilter(object):
def __init__(self, n=None, m=None, k=None, p=None, bits=None ):
self.m = m
if k > 4 or k < 1:
raise Exception('Must specify value of k between 1 and 4')
self.k = k
if bits:
self.bits = bits
else:
self.bits = BitVector( size=m )
self.rand = Random()
self.hashes = []
self.hashes.append(RSHash)
self.hashes.append(JSHash)
self.hashes.append(PJWHash)
self.hashes.append(DJBHash)
# switch between hashing techniques
self._indexes = self._rand_indexes
#self._indexes = self._hash_indexes
def __contains__(self, key):
for i in self._indexes(key):
if not self.bits[i]:
return False
return True
def add(self, key):
dupe = True
bits = []
for i in self._indexes(key):
if dupe and not self.bits[i]:
dupe = False
self.bits[i] = 1
bits.append(i)
return dupe
def __and__(self, filter):
if (self.k != filter.k) or (self.m != filter.m):
raise Exception('Must use bloom filters created with equal k / m paramters for bitwise AND')
return BloomFilter(m=self.m,k=self.k,bits=(self.bits & filter.bits))
def __or__(self, filter):
if (self.k != filter.k) or (self.m != filter.m):
raise Exception('Must use bloom filters created with equal k / m paramters for bitwise OR')
return BloomFilter(m=self.m,k=self.k,bits=(self.bits | filter.bits))
def _hash_indexes(self,key):
ret = []
for i in range(self.k):
ret.append(self.hashes[i](key) % self.m)
return ret
def _rand_indexes(self,key):
self.rand.seed(hash(key))
ret = []
for i in range(self.k):
ret.append(self.rand.randint(0,self.m-1))
return ret
if __name__ == '__main__':
e = BloomFilter(m=100, k=4)
e.add('one')
e.add('two')
e.add('three')
e.add('four')
e.add('five')
f = BloomFilter(m=100, k=4)
f.add('three')
f.add('four')
f.add('five')
f.add('six')
f.add('seven')
f.add('eight')
f.add('nine')
f.add("ten")
# test check for dupe on add
assert not f.add('eleven')
assert f.add('eleven')
# test membership operations
assert 'ten' in f
assert 'one' in e
assert 'ten' not in e
assert 'one' not in f
# test set based operations
union = f | e
intersection = f & e
assert 'ten' in union
assert 'one' in union
assert 'three' in intersection
assert 'ten' not in intersection
assert 'one' not in intersection
また、私の場合、BitVectorのcount_bits関数を高速化すると便利です。このコードをBitVector 1.5にドロップすると、より高性能なビットカウント方法が提供されます。
def fast_count_bits( self, v ):
bits = (
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 )
return bits[v & 0xff] + bits[(v >> 8) & 0xff] + bits[(v >> 16) & 0xff] + bits[v >> 24]
Parandへの反応として、「一般的な慣行はSHA1のようなものを使用して複数のハッシュを形成するようにビットを分割するように思われる」と述べていますが、それは一般的な慣行であるという意味では真実かもしれません（PyBloomも使用しています）まだそれが正しいことだという意味ではありません;-）
ブルームフィルターの場合、ハッシュ関数に必要な唯一の要件は、期待される入力が与えられると、その出力空間が均一に分布しなければならないことです。暗号化ハッシュは確かにこの要件を満たしますが、バズーカでハエを撃つようなものでもあります。
代わりに、1つのXORと1つのXORを使用する FNVハッシュを試してください。入力バイトごとの乗算は、SHA1よりも数百倍速いと推定しています：）
FNVハッシュは暗号的に安全ではありませんが、暗号化する必要はありません。わずかに不完全な雪崩の振る舞いですが、整合性チェックにも使用していません。
均一性については、2番目のリンクは32ビットFNVハッシュに対してカイ二乗検定のみを行ったことに注意してください。より多くのビットと、より良いビット分散のためにXORとMULステップを交換するFNV-1バリアントを使用することをお勧めします。ブルームフィルターの場合、出力をビット配列のインデックス範囲に均一にマッピングするなど、いくつかのキャッチがあります。可能であれば、ビット配列のサイズを最も近い2のべき乗に切り上げ、それに応じて k を調整するといいでしょう。これにより、精度が向上し、単純なXORフォールディングを使用して範囲をマッピングできます。
さらに、汎用ハッシュ。
array モジュールをご覧ください。
class Bit( object ):
def __init__( self, size ):
self.bits= array.array('B',[0 for i in range((size+7)//8)] )
def set( self, bit ):
b= self.bits[bit//8]
self.bits[bit//8] = b | 1 << (bit % 8)
def get( self, bit ):
b= self.bits[bit//8]
return (b >> (bit % 8)) & 1
FWIW、すべての // 8 および％8 操作は、＆gt;＆gt; 3 および＆ampに置き換えることができます; 0x07 。これにより、速度が若干向上する可能性があります 可能性があります。
また、 'B' および 8 を 'L' および 32 に変更すると、ほとんどの場合、より高速になります。ハードウェア。 [ 'H' と16に変更すると、ハードウェアによっては高速になる場合がありますが、疑わしいです。]
Pythonブルームフィルターの実装を http：// strombergで公開しました.dnsalias.org /〜strombrg / drs-bloom-filter /
純粋なpythonで、優れたハッシュ関数、優れた自動化されたテスト、選択されたバックエンド（ディスク、配列、mmapなど）、および __ init __ メソッドへのより直感的な引数を備えているため、多少エーテル的なデータ構造固有の調整可能パラメータではなく、理想的な要素数と望ましい最大エラー率。
ブルームフィルターバリアントとそのパフォーマンスに興味があり、ユースケースを理解しています。 ブルームフィルターバリアント（SIGCOMM、SIGMETRICSのような一流のカンファレンスで公開されたものを含む）については非常に多くのよく引用された研究作業がありますが、主流の言語ライブラリーでそれらの存在が強いとは思いません。なぜそうだと思いますか？
言語にとらわれない関心がありますが、ブルームフィルターバリアントとブルームフィルターのアプリケーションについて書いた記事を共有したいと思いました。
http://appolo85.wordpress.com/2010/08/ 03 / bloom-filter /
ブルームフィルターバリアントのユースケース、設計/実装、および他の言語のライブラリについて詳しく知りたいと思います。
ほとんどの出版物、および（コード？）ブルームのフィルターバリアントは、博士号を取得した卒業生の出版された論文数を増やすのに役立つと思いますか？
それとも、ほとんどの人が、「うまく動作する」プロダクション対応の標準ブルームフィルターの実装を台無しにしたくないということですか：D
