¿Filtro de floración moderno y de alto rendimiento en Python?

Question

Estoy buscando una implementación de filtro de floración de calidad de producción en Python para manejar un número bastante grande de artículos (digamos artículos de 100M a 1B con una tasa de falsos positivos de 0.01%).

Pybloom es una opción, pero parece estar mostrando su antigüedad a medida que arroja errores de advertencia de desaprobación en Python 2.5 de forma regular. Joe Gregorio también tiene una implementación .

Los requisitos son el rendimiento de búsqueda rápida y la estabilidad. También estoy abierto a crear interfaces Python para implementaciones de c / c ++ particularmente buenas, o incluso para Jython si hay una buena implementación de Java.

A falta de eso, ¿alguna recomendación sobre una matriz de bits / representación vectorial de bits que pueda manejar ~ 16E9 bits?

Answer 1

Finalmente encontré pybloomfiltermap . No lo he usado, pero parece que encajaría bien.

Answer 2

Hace poco también tomé este camino; aunque parece que mi aplicación fue ligeramente diferente. Estaba interesado en aproximar operaciones de conjuntos en una gran cantidad de cadenas.

Realiza la observación clave de que se requiere un vector de bits rápido . Dependiendo de lo que desee poner en su filtro de floración, es posible que también deba reflexionar sobre la velocidad de los algoritmos de hash utilizados. Puede encontrar esta biblioteca útil. También es posible que desee jugar con la técnica de números aleatorios que se utiliza a continuación que solo cambia la clave una sola vez.

En términos de implementaciones de matriz de bits no Java:

• Boost tiene dynamic_bitset
• Java tiene el BitSet incorporado

Construí mi filtro de floración usando BitVector . Pasé un tiempo perfilando y optimizando la biblioteca y contribuyendo mis parches a Avi. Vaya a ese enlace de BitVector y desplácese hacia abajo hasta los reconocimientos en v1.5 para ver detalles. Al final, me di cuenta de que el rendimiento no era un objetivo de este proyecto y decidí no usarlo.

Aquí hay un código que tenía por ahí. Puedo poner esto en el código de google en python-bloom. Sugerencias bienvenidas.

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

Además, en mi caso, me pareció útil tener una función count_bits más rápida para BitVector. Coloque este código en BitVector 1.5 y debería proporcionarle un método de conteo de bits más eficaz:

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

En reacción a Parand, decir "práctica común parece estar usando algo como SHA1 y dividir los bits para formar múltiples hashes", mientras que eso puede ser cierto en el sentido de que es una práctica común (PyBloom también lo usa), todavía no significa que sea lo correcto ;-)

Para un filtro Bloom, el único requisito que tiene una función hash es que su espacio de salida debe distribuirse uniformemente dada la entrada esperada. Si bien un hash criptográfico ciertamente cumple este requisito, también es un poco como disparar una mosca con una bazuca.

En su lugar, pruebe con el FNV Hash , que utiliza solo un XOR y uno multiplicación por byte de entrada, que calculo que es unos cientos de veces más rápido que SHA1 :)

El hash FNV no es criptográficamente seguro, pero no es necesario que lo sea. Tiene ligeramente comportamiento de avalancha imperfecto , pero tampoco lo está utilizando para verificar la integridad.

Acerca de la uniformidad, tenga en cuenta que el segundo enlace solo realizó una prueba de Chi-cuadrado para el hash FNV de 32 bits. Es mejor usar más bits y la variante FNV-1, que intercambia los pasos XOR y MUL para una mejor dispersión de bits. Para un filtro Bloom, hay algunas capturas más, como asignar la salida de manera uniforme al rango de índice de la matriz de bits. Si es posible, diría que redondea el tamaño de la matriz de bits a la potencia más cercana de 2 y ajusta k en consecuencia. De esta forma, obtienes una mayor precisión y puedes usar el plegado XOR simple para mapear el rango.

Además, aquí hay una referencia que explica por qué no desea SHA1 (o cualquier hash criptográfico) cuando necesita un hash de propósito general .

Answer 4

Mire el 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, todas las operaciones // 8 y % 8 se pueden reemplazar con > > 3 y & amp ; 0x07 . Esto puede conducir a una velocidad ligeramente mejor a riesgo de cierta oscuridad.

Además, cambiar 'B' y 8 a 'L' y 32 debería ser más rápido en la mayoría hardware. [Cambiar a 'H' y 16 podría ser más rápido en algunos hardware, pero es dudoso.]

Answer 5

Puse una implementación de filtro de floración de Python en http: // stromberg .dnsalias.org / ~ strombrg / drs-bloom-filter /

Está en Python puro, tiene buenas funciones hash, buenas pruebas automatizadas, una selección de backends (disco, matriz, mmap, más) y argumentos más intuitivos para el método __init__ , por lo que puede especificar un número ideal de elementos y la tasa de error máxima deseada, en lugar de ajustables algo etéreos, específicos de la estructura de datos.

Answer 6

Estoy muy interesado en las variantes de filtros Bloom, su rendimiento y entiendo sus casos de uso. Hay muchos trabajos de investigación bien citados sobre las variantes de filtro de Bloom (incluidos los publicados en conferencias de primer nivel como SIGCOMM, SIGMETRICS), pero no creo que su presencia sea fuerte en las bibliotecas de idiomas convencionales. ¿Por qué crees que ese es el caso?

Si bien mi interés es independiente del idioma, quería compartir un artículo que escribí sobre las variantes del filtro Bloom y las aplicaciones del filtro Bloom.

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

Me encantaría aprender más sobre sus casos de uso de las variantes del filtro Bloom, y su diseño / implementación, y bibliotecas en otros idiomas.

¿Cree que la mayoría de las publicaciones, y (¿código?) en las variantes de filtros de Bloom, solo sirven para aumentar el recuento de trabajos publicados de un graduado de doctorado?
¿O es que la mayoría de la gente no quiere meterse con una implementación de filtro de floración estándar lista para producción que "funcione bien"? : D