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

Estoy buscando una implementación de filtro bloom de calidad de producción en Python para manejar un número bastante grande de elementos (por ejemplo, de 100M a 1B con una tasa de falsos positivos de 0.01%).

Pybloom es una opción, pero parece estar mostrando su edad, ya que arroja errores de ConfrecationWarning 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 de vector de bits que pueda manejar ~ 16E9 bits?

Recientemente he ido por este camino también; aunque suena como si mi aplicación fuera ligeramente diferente. Estaba interesado en aproximar operaciones de conjuntos en un gran número de cadenas.

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

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

  • Boost tiene dynamic_bitset
  • Java tiene incorporado BitSet

Construí mi filtro de floración utilizando 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 las confirmaciones en v1.5 para ver los detalles. Al final, me di cuenta de que el rendimiento no era un objective 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 de bienvenida.

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 darle 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] 

En reacción a Parand, decir que “la 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 lo hace. t quiere decir que es lo correcto 😉

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

En su lugar, intente el FNV Hash, que usa solo un XOR y una multiplicación por byte de entrada, que estimo 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 esté. Tiene un comportamiento de avalancha levemente imperfecto , pero tampoco lo está utilizando para verificar la integridad.

Acerca de la uniformidad, tenga en cuenta que el segundo enlace solo hizo 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 uniformemente 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, obtendrá una mayor precisión y podrá utilizar el plegado XOR simple para asignar 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 .

Finalmente encontré pybloomfiltermap . No lo he usado, pero parece que encajaría a la perfección.

Mira el módulo de matriz .

 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 pueden reemplazarse con >>3 y &0x07 . Esto puede llevar a una velocidad ligeramente mejor a riesgo de cierta oscuridad.

Además, el cambio de 'B' y 8 a 'L' y 32 debería ser más rápido en la mayoría de los equipos. [Cambiar a 'H' y 16 puede ser más rápido en algunos equipos, pero es dudoso.]

He puesto 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, array, mmap, más) y argumentos más intuitivos al método __init__ , para que pueda especificar el número ideal de elementos y la tasa de error máxima deseada , en lugar de un tanto etéreo, atunables específicos de la estructura de datos.

Estoy muy interesado en las variantes de filtros Bloom, su rendimiento y entender sus casos de uso. Hay tantos trabajos de investigación bien citados sobre variantes de filtros 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 saber más sobre sus casos de uso de las variantes de filtro Bloom, su diseño / implementación y las bibliotecas en otros idiomas.

¿Crees que la mayoría de las publicaciones, y (el código?) En las variantes de filtros Bloom, solo sirven para incrementar el número de trabajos publicados de un doctorado?
¿O es que la mayoría de la gente no quiere meterse con una implementación de filtro de bloom estándar lista para producción que “funciona bien”: D