かなり多数のアイテム (0.01% の誤検知率で 1 億から 1B のアイテムなど) を処理するために、Python で実稼働品質のブルーム フィルターの実装を探しています。
Pybloomは 1 つのオプションですが、定期的に Python 2.5 で DeprecationWarning エラーをスローするため、古さを見せているようです。Joe Gregorio も実装しています。
要件は、高速検索のパフォーマンスと安定性です。また、特に優れた c/c++ 実装への Python インターフェースの作成、または優れた Java 実装があれば Jython へのインターフェースの作成にもオープンです。
それがない場合、〜16E9ビットを処理できるビット配列/ビットベクトル表現に関する推奨事項はありますか?
私も最近この道をたどりました。私のアプリケーションは少し違っていたようですが。多数の文字列に対する集合演算の近似に興味がありました。
高速なビット ベクトルが必要であるという重要な観察を行います。ブルーム フィルターに何を入れたいかによっては、使用するハッシュ アルゴリズムの速度についても考慮する必要がある場合があります。このライブラリは役に立つかもしれません。また、鍵を 1 回だけハッシュする、以下で使用する乱数手法をいじくり回すこともできます。
Java 以外のビット配列の実装に関しては、次のとおりです。
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も使用しています）、それでもそうではありません。 tはそれが正しいことを意味します;-)
ブルームフィルターの場合、ハッシュ関数の唯一の要件は、期待される入力が与えられた場合に、その出力スペースが均一に分散されている必要があることです。暗号化ハッシュは確かにこの要件を満たしていますが、バズーカでハエを撃つようなものでもあります。
代わりに、入力バイトごとに1つのXORと1つの乗算のみを使用するFNVハッシュを試してください。これは、SHA1よりも数百倍高速であると推定されます:)
FNVハッシュは暗号的に安全ではありませんが、暗号的に安全である必要はありません。わずかに不完全ななだれ動作がありますが、整合性チェックにも使用していません。
均一性については、2番目のリンクが32ビットFNVハッシュのカイ2乗検定のみを行ったことに注意してください。より多くのビットとFNV-1バリアントを使用することをお勧めします。これは、ビット分散を改善するためにXORとMULのステップを交換します。ブルームフィルターの場合、出力をビット配列のインデックス範囲に均一にマッピングするなど、さらにいくつかの問題があります。可能であれば、ビット配列のサイズを最も近い2の累乗に切り上げ、それに応じてkを調整します。そうすれば、精度が向上し、単純なXORフォールディングを使用して範囲をマッピングできます。
さらに、汎用ハッシュが必要なときにSHA1（または暗号化ハッシュ）が不要な理由を説明するリファレンスがあります。
最終的に私はpybloomfiltermapを見つけました。私は使ったことがありませんが、法案に合うようです。
配列モジュールを見てください。
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、すべての//8and操作はand% 8に置き換えることができます。これにより、あいまいさの危険を冒して速度がわずかに向上する可能性があります。>>3&0x07
また、'B'and8を'L'andに変更すると32、ほとんどのハードウェアで高速になります。[一部のハードウェアでは and 16 に変更した'H'方が速いかもしれませんが、疑わしいです。]
私はhttp://stromberg.dnsalias.org/~strombrg/drs-bloom-filter/にPythonブルームフィルターの実装を掲載しました
純粋なPythonであり、優れたハッシュ関数、優れた自動テスト、選択されたバックエンド（ディスク、アレイ、mmapなど）、およびメソッドに対するより直感的な引数を備えている__init__ため、理想的な要素数と必要な最大エラー率を指定できます。ややエーテル的な、データ構造固有の調整可能ファイルの代わりに。