Nowoczesny, wysokowydajny filtr bloom w Pythonie?

Ostatnio też szedłem tą ścieżką; choć wygląda na to, że moja aplikacja była nieco inna. Byłem zainteresowany przybliżeniem operacji set na dużej liczbie ciągów.

Dokonujesz kluczowej obserwacji, że wymagany jest wektor bitowy szybki . W zależności od tego, co chcesz umieścić w filtrze bloom, może być również konieczne zastanowienie się nad szybkością zastosowanego algorytmu mieszającego. Może się okazać, że ta biblioteka jest przydatna. Możesz również chcieć majstrować przy technika liczb losowych użyta poniżej, która tylko raz hashuje Twój klucz.

Pod względem implementacji nie-Java bit array:

• Boost ma dynamic_bitset
• Java ma wbudowany BitSet

Zbudowałem swój filtr bloom używając BitVector . Spędziłem trochę czasu na profilowaniu i optymalizacji biblioteki i dodawaniu moich łatek do Avi. Przejdź do tego łącza BitVector i przewiń w dół do potwierdzenia w wersji 1.5, aby zobaczyć szczegóły. W końcu zdałem sobie sprawę, że performance nie jest celem tego projektu i zdecydowałem się na jego wykorzystanie.

Oto jakiś kod, który mi leżał. Mogę umieścić to w Google code w python-bloom. Sugestie mile widziane.

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

Również w moim przypadku przydała mi się szybsza funkcja count_bits dla Bitvectora. Wrzuć ten kod do Bitvectora 1.5 i powinien dać ci bardziej wydajną metodę zliczania bitów:

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]

W reakcji na Paranda, powiedzenie "common practice wydaje się używać czegoś takiego jak SHA1 i dzielić bity, aby utworzyć wiele hashów", chociaż może to być prawdą w tym sensie, że jest to powszechna praktyka( PyBloom również jej używa), nadal nie oznacza to, że jest to właściwa rzecz do zrobienia ;-)

Dla filtra Bloom, jedynym wymaganiem funkcji hash jest to, że jej przestrzeń wyjściowa musi być równomiernie rozłożona, biorąc pod uwagę oczekiwane wejście. Chociaż hash kryptograficzny z pewnością spełnia ten wymóg, to też trochę jak strzelanie do muchy z bazooki.

Zamiast tego spróbuj FNV Hash który używa tylko jednego XOR i jednego mnożenia na bajt wejściowy, który szacuję, że jest kilkaset razy szybszy niż SHA1:)

Hash FNV nie jest kryptograficznie bezpieczny, ale nie potrzebujesz go. Ma lekko niedoskonałe zachowanie lawinowe, ale nie używasz go też do sprawdzania integralności.

O jednolitości, zauważ, że drugi link zrobił tylko Chi-square test dla 32-bitowego hasha FNV. Lepiej jest użyć większej ilości bitów i wariantu FNV-1, który zamienia stopnie XOR i MUL na lepszą dyspersję bitów. W przypadku filtra Bloom istnieje jeszcze kilka połowów, takich jak mapowanie wyjścia równomiernie do zakresu indeksów tablicy bitów. Jeśli to możliwe, powiedziałbym zaokrąglić rozmiar tablicy bitów do najbliższej potęgi 2 i odpowiednio dostosować k . W ten sposób uzyskasz lepszą dokładność i możesz użyć prostego XOR-folding do mapowania zasięg.

DODATKOWO, tutaj jest odniesienie wyjaśniające, dlaczego nie chcesz SHA1 (lub jakiegokolwiek kryptograficznego skrótu), gdy potrzebujesz ogólnego skrótu .

Spójrz na moduł 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, wszystkie operacje //8 i % 8 można zastąpić >>3 i &0x07. To może prowadzić do nieco lepszej prędkości, ryzykując pewną ciemność.

Zmiana 'B' i 8 na 'L' i 32 powinna być szybsza na większości urządzeń. [Zmiana na 'H' i 16 może być szybsza na jakimś sprzęcie, ale wątpliwe.]

Umieściłem implementację Pythona bloom filter na http://stromberg.dnsalias.org/ ~ strombrg / drs-bloom-filter /

Jest w czystym Pythonie, ma dobre funkcje hashowe, dobre testy automatyczne, wybór backendów (dysk, tablica, mmap, więcej) i bardziej intuicyjne argumenty do metody __init__, dzięki czemu można określić idealną liczbę elementów i żądany maksymalny poziom błędu, zamiast nieco eterycznych, specyficznych dla struktury danych tunabli.

Jestem bardzo zainteresowany wariantami filtrów Bloom, ich wydajnością i zrozumieniem ich zastosowań. Istnieje tak wiele dobrze cytowanych prac badawczych nad wariantami filtrów Bloom( w tym opublikowanych w najlepszych konferencjach, takich jak SIGCOMM, SIGMETRICS), ale nie sądzę, aby ich obecność była silna w głównych bibliotekach językowych. Jak myślisz, dlaczego tak jest?

Chociaż interesuje mnie język-agnostyka, chciałem podzielić się artykułem, który napisałem o wariantach filtrów Bloom i zastosowaniach Filtr Bloom.

Http://appolo85.wordpress.com/2010/08/03/bloom-filter/

Chciałbym dowiedzieć się więcej o ich zastosowaniach wariantów filtrów Bloom, ich projektowaniu/implementacji oraz bibliotekach w innych językach.

Czy uważasz, że większość publikacji i (Kod?) na wariantach filtrów Bloom służy tylko do zwiększenia liczby opublikowanych prac doktoranta?
Czy jest tak, że większość ludzi nie chce zadzierać z gotowym do produkcji standardowa implementacja filtra bloom, która "działa dobrze": d