Filtro de Bloom moderno e de alto desempenho em Python?

Question

Estou procurando uma implementação de filtro de qualidade de produção de produção em Python para lidar com um número bastante grande de itens (digamos de 100 milhões a 1B com itens com 0,01% de taxa positiva falsa).

Pybloom é uma opção, mas parece estar mostrando sua idade, pois lança erros de depreciação no Python 2.5 regularmente. Joe Gregorio também tem uma implementação.

Os requisitos são o desempenho e a estabilidade da pesquisa rápida. Também estou aberto a criar interfaces Python para implementações particularmente boas do C/C ++, ou mesmo para o Jython, se houver uma boa implementação de Java.

Na falta disso, alguma recomendação sobre uma representação de um vetor de matriz / bits que pode lidar com ~ 16e9 bits?

Answer 1

Eventualmente eu encontrei pybloomfiltermap. Eu não usei, mas parece que se encaixaria na conta.

Answer 2

Recentemente, segui esse caminho também; Embora pareça que meu aplicativo foi um pouco diferente. Eu estava interessado em aproximar as operações definidas em um grande número de cordas.

Você faz a chave principal de que um velozes Vetor de bit é necessário. Dependendo do que você deseja colocar no filtro Bloom, também pode precisar pensar em alguma velocidade do (s) algoritmo (s) de hash. Você pode encontrar isso biblioteca útil. Você também pode querer mexer com a técnica de número aleatório usado abaixo que só houver sua chave uma única vez.

Em termos de implementações de matriz de bits não Java:

• Boost tem dinâmico_bitset
• Java tem o embutido Bitset

Eu construí meu filtro Bloom usando BitVector. Passei algum tempo perfilando e otimizando a biblioteca e contribuindo com meus patches para Avi. Vá para esse link BitVector e role para baixo até os agradecimentos na v1.5 para ver os detalhes. No final, percebi que o desempenho não era um objetivo deste projeto e decidi não usá -lo.

Aqui está algum código que eu tinha por aí. Posso colocar isso no código do Google no Python-Bloom. Sugestões são bem -vindas.

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

Além disso, no meu caso, achei útil ter uma função Count_bits mais rápida para o BitVector. Solte este código no BitVector 1.5 e deve fornecer um método de contagem de bits mais com desempenho:

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

Em reação ao Parand, dizer "a prática comum parece estar usando algo como SHA1 e dividir os bits para formar vários hashes", enquanto isso pode ser verdade no sentido de que é prática comum (o pybloom também o usa), ainda não é t significa que é a coisa certa a fazer ;-)

Para um filtro Bloom, o único requisito que uma função de hash tem é que seu espaço de saída deve ser distribuído uniformemente, dada a entrada esperada. Embora um hash criptográfico certamente atenda a esse requisito, também é um pouco como gravar uma mosca com uma bazuca.

Em vez disso, tente o FNV Hash que usa apenas um XOR e uma multiplicação por byte de entrada, que eu estimo é algumas centenas de vezes mais rápido que o sha1 :)

O hash da FNV não é criptograficamente seguro, mas você não precisa ser. Tem um pouco comportamento imperfeito de avalanche, mas você também não está usando para verificação de integridade.

Sobre a uniformidade, observe que o segundo link fez apenas um teste qui-quadrado para o hash de FNV de 32 bits. É melhor usar mais bits e a variante FNV-1, que troca o XOR e os passos do MUL para uma melhor dispersão de bits. Para um filtro Bloom, há mais algumas capturas, como mapear a saída uniformemente para o alcance do índice da matriz de bits. Se possível, eu diria arredondar o tamanho da gravação de bits para a potência mais próxima de 2 e ajustar k adequadamente. Dessa forma, você obtém melhor precisão e pode usar a dobra xor simples para mapear o intervalo.

Além disso, aqui está uma referência explicando por que você não quer SHA1 (ou qualquer hash criptográfico) quando você precisar um hash de propósito geral.

Answer 4

Olhe para a variedade módulo.

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, todos os //8 e % 8 Operações podem ser substituídas por >>3 e &0x07. este poderia levar a uma velocidade um pouco melhor no risco de alguma obscuridade.

Além disso, mudando 'B' e 8 para 'L' e 32 deve ser mais rápido na maioria dos hardware. [Mudando para 'H' e 16 pode ser mais rápido em algum hardware, mas é duvidoso.

Answer 5

Eu coloquei uma implementação do filtro de Bloom Python em http://stromberg.dnsalias.org/~strombrg/drs-low-filter/

Está em python puro, tem boas funções de hash, bons testes automatizados, uma seleção de back -end (disco, matriz, mmap, mais) e argumentos mais intuitivos para o __init__ Método, para que você possa especificar um número ideal de elementos e a taxa máxima de erro desejada, em vez de um tanto etéreo, tunable específico de dados.

Answer 6

Estou profundamente interessado em variantes de filtros de Bloom, seu desempenho e entender seus casos de uso. Existem tantos trabalhos de pesquisa bem citados sobre variantes de filtro Bloom (incluindo as publicadas em conferências de alto nível como SigComm, Sigmetrics), mas não acho que a presença deles seja forte nas bibliotecas de idiomas convencionais. Por que você acha que é esse o caso?

Embora meu interesse seja agnóstico da linguagem, eu queria compartilhar um artigo que escrevi sobre variantes de filtro Bloom e aplicações do filtro Bloom.

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

Eu adoraria aprender mais sobre seus casos de uso das variantes de filtro Bloom, seu design/implementação e bibliotecas em outros idiomas.

Você acha que a maioria das publicações e (código?) Em variantes de filtros Bloom servem apenas para incrementar a contagem de papel publicada de um graduado de doutorado?
Ou é que a maioria das pessoas não quer mexer com uma implementação padrão de filtro Bloom pronta para produção que "funciona muito bem": D