Современный, высокопроизводительный фильтр цветения в Python?

Ответ 1

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

Ответ 2

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

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

В терминах реализаций битовых массивов, отличных от 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]

Ответ 3

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

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

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

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

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

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

Ответ 4

Посмотрите на модуль 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 может быть быстрее на каком-то оборудовании, но это сомнительно.]

Ответ 5

Я включил реализацию фильтра цветения python на http://stromberg.dnsalias.org/~strombrg/drs-bloom-filter/

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

Ответ 6

Я очень интересуюсь вариантами фильтров Bloom, их характеристиками и пониманием их вариантов использования. Существует так много хорошо проработанных исследовательских работ по вариантам фильтров Bloom (включая публикации, опубликованные на первоклассных конференциях, таких как SIGCOMM, SIGMETRICS), но я не думаю, что их присутствие сильное в основных языковых библиотеках. Почему вы думаете, что дело?

Хотя мой интерес к языку-агностик, я хотел поделиться статьей, которую я написал о вариантах фильтра Bloom, и приложениях фильтра Bloom.

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

Мне бы хотелось узнать больше об их вариантах использования вариантов фильтра Bloom, их дизайне/реализации и библиотеках на других языках.

Считаете ли вы, что большинство публикаций и (код?) в вариантах фильтров Bloom служат только для увеличения количества опубликованных статей в аспирантуре?

Или дело в том, что большинство людей не хотят возиться с стандартной версией фильтра цветного производства, которая "работает просто отлично": D

Ответ 7

Вы можете попробовать с it.unimi.dsi.util.BloomFilter Утилиты DSI.