Современный высокопроизводительный фильтр Блума в Python?

Недавно я тоже пошел по этому пути; хотя похоже, что мое приложение было немного другим. Меня интересовали аппроксимирующие операции над множествами для большого количества строк.

Вы делаете ключевое наблюдение, что требуется быстрый битовый вектор. В зависимости от того, что вы хотите поместить в свой фильтр Блума, вам также может потребоваться подумать о скорости используемых алгоритмов хеширования. Вы можете найти эту библиотеку полезной. Вы также можете поэкспериментировать с методом случайных чисел, используемым ниже, который хэширует ваш ключ только один раз.

С точки зрения реализации битового массива, отличного от Java:

• Boost имеет dynamic_bitset
• Java имеет встроенный BitSet.

Я создал фильтр Блума, используя BitVector. Я потратил некоторое время на профилирование и оптимизацию библиотеки, а также добавил свои патчи в Avi. Перейдите по этой ссылке BitVector и прокрутите вниз до благодарностей в версии 1.5, чтобы увидеть подробности. В конце концов я понял, что производительность не является целью этого проекта, и решил не использовать его.

Вот какой-то код, который у меня лежал. Я могу разместить это в коде Google на python-bloom. Предложения приветствуются.

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

Кроме того, в моем случае полезно иметь более быструю функцию count_bits для BitVector. Поместите этот код в BitVector 1.5, и он должен дать вам более производительный метод подсчета битов:

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]

В ответ на Паранд, говоря, что «обычная практика, похоже, использует что-то вроде SHA1 и разделяет биты для формирования нескольких хэшей», хотя это может быть правдой в том смысле, что это обычная практика (PyBloom также использует это), это все еще не так. значит это правильно ;-)

Для фильтра Блума единственное требование к хеш-функции состоит в том, что ее выходное пространство должно быть равномерно распределено с учетом ожидаемого ввода. Хотя криптографический хеш, безусловно, соответствует этому требованию, он также немного напоминает стрельбу по мухе из базуки.

Вместо этого попробуйте хэш FNV, который использует только одно XOR и одно умножение на входной байт. , который, по моим оценкам, в несколько сотен раз быстрее, чем SHA1 :)

Хэш FNV не является криптографически безопасным, но вам это и не нужно. Он имеет несколько несовершенный лавинное поведение, но вы также не используете его для проверки целостности.

Что касается единообразия, обратите внимание, что вторая ссылка выполняла только тест Хи-квадрат для 32-битного хэша FNV. Лучше использовать больше битов и вариант FNV-1, который меняет местами шаги XOR и MUL для лучшей дисперсии битов. Для фильтра Блума есть еще несколько уловок, например, однородное сопоставление вывода с диапазоном индексов битового массива. Если возможно, я бы округлил размер битового массива до ближайшей степени 2 и соответствующим образом отрегулировал k. Таким образом, вы получите лучшую точность и сможете использовать простое XOR-сложение для отображения диапазона.

Кроме того, вот ссылка, объясняющая, почему вам не нужен SHA1 (или любой криптографический хеш), когда вам нужен хэш общего назначения.

В конце концов я нашел pybloomfiltermap. Я не использовал его, но, похоже, он соответствует всем требованиям.

Посмотрите на модуль 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, все операции //8 и % 8 можно заменить на >>3 и &0x07. Это может привести к немного большей скорости с риском некоторой неясности.

Кроме того, изменение 'B' и 8 на 'L' и 32 должно выполняться быстрее на большинстве аппаратных средств. [Изменение на 'H' и 16 может быть быстрее на некотором оборудовании, но это сомнительно.]

Прошло почти десять лет с тех пор, как здесь были самые последние ответы. И времена меняются.

Похоже, самым популярным поддерживаемым пакетом фильтра Блума в конце 2019 года стал следующий: https://github.com/joseph-fox/python-bloomfilter, доступно на PyPi как pybloom_live: https://pypi.org/project/pybloom_live/

Я разместил реализацию фильтра Блума на Python по адресу http://stromberg.dnsalias.org/~strombrg/drs-bloom-filter/

Он написан на чистом питоне, имеет хорошие хеш-функции, хорошие автоматические тесты, выбор бэкендов (диск, массив, mmap и т. д.) и более интуитивно понятные аргументы для метода __init__, так что вы можете указать идеальное количество элементов и желаемую максимальную частоту ошибок. , вместо несколько эфирных, специфичных для структуры данных настраиваемых параметров.