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

Question

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 elementos 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 an implementation.

Los requisitos son un rendimiento de búsqueda rápida y estabilidad. 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.

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

Answer 1

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

Answer 2

Mire el módulo 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 puede ser sustituido por >>3 y &0x07. Este puede conducir a una velocidad ligeramente mejor a riesgo de algo de oscuridad.

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

Answer 3

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 este library ú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:

• Boost tiene dynamic_bitset
• Java se ha construido en BitSet

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 


# 
# 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 he encontrado que es útil tener una función count_bits más rápido para BitVector. Suelta este código en BitVector 1.5 y se le debe dar un método de conteo de bits con más prestaciones:

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 4

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 principales bibliotecas de idiomas. ¿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 gustaría aprender más sobre sus casos de uso de las variantes de filtro Bloom, y su diseño/aplicació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

Answer 5

En respuesta a Parand, diciendo que "la práctica común parece estar usando 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 significa 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 lugar de tratar la FNV Hash que utiliza sólo un XOR y una multiplicación por byte de entrada, que estimo es unos pocos cientos de veces más rápido que SHA1 :)

El hash FNV no es criptográficamente seguro, pero no lo hace necesito que sea. Tiene un poco de imperfect avalanche behaviour, pero tampoco lo está utilizando para la verificación de 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 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 a general purpose hash.

Answer 6

Puedes probar con it.unimi.dsi.util.BloomFilter de The DSI Utilities.

Answer 7

He puesto una implementación de filtro Bloom pitón en http://stromberg.dnsalias.org/~strombrg/drs-bloom-filter/

Es en Python puro, tiene buenas funciones hash, buenas pruebas automatizadas, una selección de backends (disco, matriz MMAP, más) y más intuitiva argumentos al método __init__, por lo que puede especificar una cantidad ideal de elementos y la tasa de error máxima deseada, en lugar de ajustes ajustables de etérea, específicos de la estructura.