Moderne, de haute performance filtre de bloom en Python?

Je suis récemment allé en bas de ce chemin; si elle ressemble à ma demande a été légèrement différente. J'ai été intéressé par approximation de l'ensemble des opérations relatives à un grand nombre de chaînes.

Vous faites la clé de l'observation qu'un rapide vecteur de bits est requis. Selon ce que vous voulez mettre dans votre filtre de bloom, vous pouvez également besoin de penser à la vitesse de l'algorithme de hachage(s) utilisé. Vous trouverez peut-être ce bibliothèque utile. Vous pouvez aussi bricoler avec le nombre aléatoire technique utilisée ci-dessous que seuls les hachages votre touche une seule fois.

En termes de non-Java tableau de bits implémentations:

• Boost a dynamic_bitset
• Java a construit dans le BitSet

J'ai construit mes fleurs filtre à l'aide de BitVector. J'ai passé un certain temps de profilage et de l'optimisation de la bibliothèque et de contribuer en retour mes patches pour Avi. Aller à cette BitVector lien et faites défiler vers le bas pour les accusés de réception dans v1.5 pour plus de détails. En fin de compte, j'ai réalisé que le rendement n'était pas l'objectif de ce projet et a décidé à l'encontre de l'utiliser.

Voici un code que j'avais traîner. Je peut mettre cela sur google code en python-floraison. Suggestions de bienvenue.

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
#
# [email protected] /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

Aussi, dans mon cas, j'ai trouvé utile de disposer d'une plus rapide count_bits fonction pour BitVector. Déposer ce code dans BitVector 1,5 et il devrait vous donner un peu plus performant méthode de comptage:

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]

Finalement, j'ai trouvé pybloomfiltermap. Je ne l'ai pas utilisé, mais il semble qu'il faudrait adapter le projet de loi.

J'ai mis en place un python bloom filtre de mise en œuvre au http://stromberg.dnsalias.org/~strombrg/drs-bloom-filtre/

C'est dans le plus pur python, a de bonnes fonctions de hachage, de bons tests automatisés, une sélection de backends (disque, tableau, mmap, de plus en plus) et plus intuitive des arguments à l' __init__ méthode, de sorte que vous pouvez spécifier un nombre idéal d'éléments et maximale souhaitée pour le taux d'erreur, au lieu de un peu éthérée, discbased spécifique de paramètres.