Un filtre bloom moderne et performant en Python ?

Question

Je suis à la recherche d'une implémentation de filtre bloom de qualité production en Python pour traiter un nombre assez important d'éléments (disons 100M à 1B éléments avec un taux de faux positifs de 0,01%).

Pybloom est une option, mais elle semble montrer son âge car elle génère régulièrement des erreurs DeprecationWarning sous Python 2.5. Joe Gregorio a également une mise en œuvre .

Les exigences sont des performances de recherche rapides et la stabilité. Je suis également ouvert à la création d'interfaces Python vers des implémentations c/c++ particulièrement bonnes, ou même vers Jython s'il existe une bonne implémentation Java.

En l'absence de cela, avez-vous des recommandations sur un tableau de bits / une représentation de vecteur de bits qui peut gérer ~16E9 bits ?

Answer 1

J'ai récemment suivi cette voie également, bien que ma demande semble être légèrement différente. J'étais intéressé par l'approximation des opérations sur un grand nombre de chaînes de caractères.

Vous faites l'observation clé qu'un rapide est nécessaire. En fonction de ce que vous voulez mettre dans votre filtre bloom, vous devrez peut-être aussi réfléchir à la vitesse du ou des algorithmes de hachage utilisés. Vous pouvez trouver ceci bibliothèque utile. Vous pouvez également utiliser la technique des nombres aléatoires utilisée ci-dessous, qui permet de hacher votre clé une seule fois.

En termes d'implémentations de tableaux de bits non-Java :

• Boost a dynamic_bitset
• Java dispose d'une fonction intégrée BitSet

J'ai construit mon filtre bloom en utilisant BitVector . J'ai passé un certain temps à profiler et à optimiser la bibliothèque et à reverser mes correctifs à Avi. Allez sur ce lien BitVector et descendez jusqu'aux remerciements dans la v1.5 pour voir les détails. Finalement, j'ai réalisé que les performances n'étaient pas un objectif de ce projet et j'ai décidé de ne pas l'utiliser.

Voici un code que j'avais sous la main. Je vais peut-être le mettre sur google code à python-bloom. Les suggestions sont les bienvenues.

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

De plus, dans mon cas, j'ai trouvé utile d'avoir une fonction count_bits plus rapide pour BitVector. Ajoutez ce code à BitVector 1.5 et vous obtiendrez une méthode de comptage des bits plus performante :

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]

Answer 2

En réaction à Parand, qui dit "la pratique courante semble être d'utiliser quelque chose comme SHA1 et de diviser les bits pour former des hachages multiples", bien que cela puisse être vrai dans le sens où c'est une pratique courante (PyBloom l'utilise aussi), cela ne veut pas dire que c'est la bonne chose à faire ;-)

Pour un filtre de Bloom, la seule exigence d'une fonction de hachage est que son espace de sortie doit être uniformément distribué compte tenu de l'entrée attendue. Bien qu'un hachage cryptographique réponde certainement à cette exigence, c'est aussi un peu comme tirer sur une mouche avec un bazooka.

Essayez plutôt le FNV Hash qui n'utilise qu'un XOR et une multiplication par octet d'entrée, ce qui, selon mes estimations, est quelques centaines de fois plus rapide que SHA1 :)

Le hachage du FNV n'est pas cryptographiquement sûr, mais vous n'avez pas besoin qu'il le soit. Il a légèrement comportement imparfait en cas d'avalanche mais vous ne l'utilisez pas non plus pour le contrôle d'intégrité.

À propos de l'uniformité, notez que le deuxième lien n'a effectué un test du chi carré que pour le hachage 32 bits du FNV. Il est préférable d'utiliser plus de bits et la variante FNV-1, qui échange les étapes XOR et MUL pour une meilleure dispersion des bits. Pour un filtre de Bloom, il y a un peu plus de problèmes, comme le mappage uniforme de la sortie sur la plage d'index du tableau de bits. Si possible, je dirais d'arrondir la taille du tableau de bits à la puissance de 2 la plus proche et d'ajuster k en conséquence. De cette façon, vous obtenez une meilleure précision et vous pouvez utiliser un simple pliage XOR pour cartographier la portée.

En outre, voici une référence expliquant pourquoi vous ne voulez pas de SHA1 (ou tout autre hachage cryptographique) lorsque vous avez besoin de un hachage à usage général .

Answer 3

Finalement, j'ai trouvé pybloomfiltermap . Je ne l'ai pas utilisé, mais il semble qu'il pourrait faire l'affaire.

Answer 4

Regardez le array module.

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, tous les //8 y % 8 peuvent être remplacées par >>3 y &0x07 . Ce site puede conduisent à une vitesse légèrement supérieure au risque d'une certaine obscurité.

De même, la modification 'B' y 8 a 'L' y 32 devrait être plus rapide sur la plupart des matériels. [Le passage à 'H' et 16 pourrait être plus rapide sur certains matériels, mais c'est douteux].

Answer 5

J'ai mis en place une implémentation du filtre bloom en python à l'adresse suivante http://stromberg.dnsalias.org/~strombrg/drs-bloom-filter/

Il est en pur python, possède de bonnes fonctions de hachage, de bons tests automatisés, une sélection de backends (disque, tableau, mmap, plus) et des arguments plus intuitifs pour la fonction __init__ afin que vous puissiez spécifier un nombre idéal d'éléments et le taux d'erreur maximal souhaité, au lieu d'utiliser des paramètres spécifiques à la structure de données quelque peu éthérés.