Filtro bloom moderno e ad alte prestazioni in Python?

Question

Sto cercando un'implementazione del filtro bloom di qualità di produzione in Python per gestire un numero abbastanza grande di articoli (diciamo articoli da 100M a 1B con tasso di falsi positivi dello 0,01%).

Pybloom è un'opzione ma sembra mostrare la sua età mentre genera Deprecazione Errori di avviso su Python 2.5 su base regolare. Joe Gregorio ha anche un'implementazione .

I requisiti sono prestazioni di ricerca rapida e stabilità. Sono anche aperto alla creazione di interfacce Python per implementazioni c / c ++ particolarmente buone, o anche a Jython se c'è una buona implementazione Java.

In mancanza di ciò, qualche consiglio su una rappresentazione vettoriale di array di bit / bit che può gestire ~ 16E9 bit?

Answer 1

Alla fine ho trovato pybloomfiltermap . Non l'ho usato, ma sembra che si adatterebbe al conto.

Answer 2

Di recente ho seguito anche questo percorso; anche se sembra che la mia applicazione sia leggermente diversa. Ero interessato ad approssimare le operazioni sul set su un gran numero di stringhe.

Fai l'osservazione chiave secondo cui è richiesto un vettore bit veloce . A seconda di cosa vuoi inserire nel tuo filtro bloom, potresti anche dover riflettere sulla velocità degli algoritmi di hashing utilizzati. Questa library potrebbe essere utile. Potresti anche voler armeggiare con la tecnica dei numeri casuali utilizzata di seguito che esegue l'hashing della chiave solo una volta.

In termini di implementazioni di array di bit non Java:

• Boost ha dynamic_bitset
• Java ha incorporato BitSet

Ho creato il mio filtro bloom utilizzando BitVector . Ho trascorso un po 'di tempo a profilare e ottimizzare la libreria e a contribuire con le mie patch ad Avi. Vai a quel link BitVector e scorri verso il basso fino ai riconoscimenti in v1.5 per vedere i dettagli. Alla fine, mi sono reso conto che la performance non era un obiettivo di questo progetto e ho deciso di non usarlo.

Ecco del codice che avevo in giro. Potrei metterlo sul codice di Google su Python-Bloom. Suggerimenti benvenuti.

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

Inoltre, nel mio caso ho trovato utile avere una funzione count_bits più veloce per BitVector. Rilascia questo codice in BitVector 1.5 e dovrebbe darti un metodo di conteggio dei bit più 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 3

In reazione a Parand, dire "la pratica comune sembra usare qualcosa come SHA1 e dividere i bit per formare più hash", mentre ciò può essere vero nel senso che è pratica comune (PyBloom lo usa anche), non significa ancora che sia la cosa giusta da fare ;-)

Per un filtro Bloom, l'unico requisito richiesto da una funzione hash è che il suo spazio di output debba essere distribuito uniformemente alla luce dell'input previsto. Mentre un hash crittografico soddisfa certamente questo requisito, è anche un po 'come sparare a una mosca con un bazooka.

Prova invece il FNV Hash che utilizza solo un XOR e uno la moltiplicazione per byte di input, che stima sia alcune centinaia di volte più veloce di SHA1 :)

L'hash di FNV non è crittograficamente sicuro, ma non è necessario che lo sia. Ha leggermente comportamento imperfetto delle valanghe , ma non lo stai nemmeno usando per il controllo dell'integrità.

Per quanto riguarda l'uniformità, si noti che il secondo collegamento ha eseguito solo un test Chi-quadrato per l'hash FNV a 32 bit. È meglio usare più bit e la variante FNV-1, che scambia i passi XOR e MUL per una migliore dispersione dei bit. Per un filtro Bloom, ci sono alcune catture in più, come mappare l'output uniformemente all'intervallo di indice dell'array di bit. Se possibile, direi di arrotondare la dimensione dell'array di bit alla potenza più vicina di 2 e di regolare k di conseguenza. In questo modo otterrai una maggiore precisione e puoi utilizzare la semplice piegatura XOR per mappare l'intervallo.

Inoltre, ecco un riferimento che spiega perché non vuoi SHA1 (o qualsiasi hash crittografico) quando hai bisogno di un hash per scopi generici .

Answer 4

Guarda il modulo 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, tutte le operazioni // 8 e % 8 possono essere sostituite con > > 3 e & amp ; 0x07 . Questo può portare a una velocità leggermente migliore a rischio di oscurità.

Inoltre, cambiando 'B' e 8 in 'L' e 32 dovrebbe essere più veloce sulla maggior parte hardware. [Il passaggio a 'H' e 16 potrebbe essere più veloce su alcuni componenti hardware, ma è dubbio.]

Answer 5

Ho implementato un'implementazione del filtro bloom Python all'indirizzo http: // stromberg .dnsalias.org / ~ strombrg / DRS-bloom-filtro /

È in puro pitone, ha buone funzioni hash, buoni test automatizzati, una selezione di backend (disco, array, mmap, altro) e argomenti più intuitivi per il metodo __init__ , quindi puoi specificare un numero ideale di elementi e il tasso di errore massimo desiderato, anziché parametri sintonizzabili piuttosto eterogenei e specifici della struttura di dati.

Answer 6

Sono profondamente interessato alle varianti dei filtri Bloom, alle loro prestazioni e alla comprensione dei loro casi d'uso. Ci sono così tanti lavori di ricerca ben citati sulle varianti del filtro Bloom (compresi quelli pubblicati in conferenze di alto livello come SIGCOMM, SIGMETRICS), ma non credo che la loro presenza sia forte nelle biblioteche di lingua tradizionali. Perché pensi che sia così?

Mentre il mio interesse è indipendente dalla lingua, volevo condividere un articolo che ho scritto sulle varianti del filtro Bloom e sulle applicazioni del filtro Bloom.

http://appolo85.wordpress.com/2010/08/08/ 03 / bloom-filtro /

Mi piacerebbe saperne di più sui loro casi d'uso delle varianti del filtro Bloom, sulla loro progettazione / implementazione e sulle librerie in altre lingue.

Pensi che la maggior parte delle pubblicazioni, e (codice?) sulle varianti dei filtri Bloom, servano solo ad aumentare il conteggio dei documenti pubblicati di un dottorando?
O è che la maggior parte delle persone non vuole fare confusione con un'implementazione del filtro bloom standard pronta per la produzione che "funziona bene" : D