python jython bloom-filter

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



jython bloom-filter (7)

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 se pueden reemplazar por >>3 y &0x07 . Esto puede conducir a una velocidad ligeramente mejor a riesgo de algo de oscuridad.

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

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

Pybloom es una opción, pero parece estar mostrando su edad, ya que arroja errores de DeprecationWarning en Python 2.5 de forma regular. Joe Gregorio también tiene una implementación .

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

Al carecer de eso, ¿hay alguna recomendación sobre una representación de vector de bits / matriz de bits que pueda manejar ~ 16E9 bits?

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

Estoy muy interesado en las variantes de filtros Bloom, su rendimiento y entiendo sus casos de uso. Hay tantos trabajos de investigación bien citados sobre las variantes del filtro 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 las bibliotecas en otros idiomas.

¿Cree que la mayoría de las publicaciones, y (¿el código?) En las variantes de filtros Bloom, solo sirven para incrementar el conteo de papel publicado de un 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 "funciona bien": D

Recientemente también fui por este camino; aunque parece que mi aplicación fue ligeramente diferente. Estaba interesado en aproximar operaciones de conjunto en una gran cantidad de cadenas.

Usted hace la observación clave de que se requiere un vector de bits rápido . Dependiendo de lo que quieras poner en tu filtro bloom, también deberás pensar en la velocidad del algoritmo hash utilizado. 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 hashes su clave una sola vez.

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

Construí mi filtro bloom usando BitVector . Pasé algún tiempo perfilando y optimizando la biblioteca y contribuyendo con 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 # # [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

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 le dará un método de recuento 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]

He puesto una implementación de filtro python bloom 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 una cantidad ideal de elementos y la tasa de error máxima deseada , en lugar de elementos ajustables específicos de la estructura de datos, algo etéreos.

En reacción a Parand, diciendo que "la práctica común parece usar algo como SHA1 y dividir los bits para formar hash múltiples", 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 quiero 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 uniformemente dada la entrada esperada. Si bien un hash criptográfico cumple con este requisito, también es un poco como disparar una mosca con un bazooka.

En su lugar, intente con FNV Hash, que usa solo un XOR y una multiplicación por byte de entrada, lo cual 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 sea. Tiene un comportamiento de avalancha ligeramente 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 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 Bloom Filter, hay algunas capturas más, como asignar la salida de manera uniforme al rango de índice de la matriz de bits. Si es posible, yo diría redondear el tamaño de la matriz de bits a la potencia más cercana de 2 y ajustar k en consecuencia. De esta forma obtendrás una mayor precisión y puedes usar un 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 .