الحديثة عالية الأداء بلوم مرشح في الثعبان ؟

Question

أنا أبحث عن جودة الإنتاج بلوم تصفية التنفيذ في بيثون للتعامل مع بأعداد كبيرة من عناصر (أقول 100M إلى 1B البنود مع 0.01% معدل الإيجابية الكاذبة).

Pybloom هو خيار واحد ولكن يبدو أن عرض عصرها كما يلقي DeprecationWarning أخطاء في بايثون 2.5 على أساس منتظم.جو غريغوريو أيضا التنفيذ.

متطلبات بحث سريع الأداء والاستقرار.أنا أيضا مفتوحة إلى خلق الثعبان واجهات جيد وخاصة c/c++ تطبيقات أو حتى Jython إذا كان هناك تنفيذ جافا.

تفتقر إلى ذلك ، فإن أي توصيات بشأن صفيف بت / بت ناقلات التمثيل التي يمكن التعامل مع ~16E9 بت ؟

Answer 1

وأخيرا وجدت pybloomfiltermap . أنا لم تستخدم، ولكن يبدو انها تريد ان صالح مشروع القانون.

Answer 2

ذهبت مؤخرا في هذا الطريق ؛ على الرغم من أنه يبدو أن طلبي كان مختلف قليلا.أنا مهتم في تقارب مجموعة العمليات على عدد كبير من السلاسل.

كنت لا تجعل الملاحظة الرئيسية التي سريع بت ناقلات مطلوب.اعتمادا على ما كنت تريد أن تضع في ازهر فلتر, قد تحتاج أيضا إلى إعطاء بعض الفكر سرعة خوارزمية التجزئة(s) تستخدم.قد تجد هذا مكتبة مفيدا.قد تحتاج أيضا إلى العبث مع عدد عشوائي التقنية المستخدمة أدناه فقط التجزئة الرئيسية الخاصة بك مرة واحدة.

حيث من غير جافا بت مجموعة تطبيقات:

• دفعة قد dynamic_bitset
• جافا المضمنة في BitSet

لقد بنيت حياتي تزدهر تصفية باستخدام BitVector.قضيت بعض الوقت والتنميط والاستفادة من المكتبة و المساهمة ظهري بقع Avi.تذهب إلى أن BitVector رابط انتقل لأسفل إلى الاعترافات في v1.5 لمعرفة التفاصيل.في النهاية أدركت أن الأداء لم يكن الهدف من هذا المشروع وقررت ضد استخدامه.

هنا بعض التعليمات البرمجية لدي حول الكذب.كنت قد وضعت هذا على جوجل كود في بيثون-ازهر.اقتراحات موضع ترحيب.

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

كما في حالتي أنا وجدت أنه من المفيد أن يكون أسرع count_bits وظيفة BitVector.إسقاط هذا القانون في BitVector 1.5 وينبغي أن تعطيك أكثر performant بت طريقة العد:

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 3

في رد فعل على Parand، قائلا "ممارسة شائعة ويبدو أن استخدام شيء من هذا القبيل SHA1 وتقسيم بت لتشكيل التجزئة متعددة"، في حين أنه قد يكون صحيحا، بمعنى أنه من الشائع (PyBloom كما يستخدم ذلك)، فإنه لا يزال لا يعني أنه هو الشيء الصحيح الذي ينبغي عمله. -)

لمرشح بلوم، والشرط الوحيد وظيفة تجزئة لديه هو أن الفضاء انتاجها يجب بشكل موحد وزعت منح الإدخال المتوقع. في حين أن تجزئة التشفير يفي بالتأكيد هذا المطلب، كما انها قليلا مثل اطلاق النار على الطاير مع مدفع بازوكا.

وحاول بدلا من ذلك FNV تجزئة الذي يستخدم فقط XOR واحد واحد الضرب لكل بايت المدخلات، التي أقدر على بعد بضعة مئات المرات أسرع من SHA1:)

وتجزئة FNV ليست آمنة بشكل مشفر، ولكن لا تحتاج أن تكون. لديها قليلا الكمال السلوك الانهيار ، ولكن كنت لا تستخدم لفحص سلامة سواء.

وعن التوحيد، لاحظ أن الرابط الثاني لم مجرد اختبار مربع كاي لتجزئة FNV 32 بت. فمن الأفضل لاستخدام أكثر من بت والبديل FNV-1، الذي مقايضة على XOR والخطوات MUL لأفضل قليلا والتشتت. لتصفية بلوم، وهناك عدد قليل من أكثر المصيد، مثل رسم خرائط الانتاج بشكل موحد على نطاق المؤشر للمجموعة الشيء. إذا كان ذلك ممكنا، وانا اقول جولة يصل حجم مصفوفة قليلا إلى أقرب سلطة 2 وضبط <م> ك وفقا لذلك. وبهذه الطريقة يمكنك الحصول على دقة أفضل ويمكنك استخدام بسيط XOR للطي لتعيين النطاق.

وبالإضافة إلى ذلك، وهنا إشارة يشرح لماذا كنت لا تريد SHA1 (أو أي تجزئة التشفير) عند الحاجة <لأ href = "https://web.archive.org/web/20120722074824/http://bretm. home.comcast.net/~bretm/hash/9.html "يختلط =" نوفولو noreferrer "> غرض تجزئة عام .

Answer 4

href="http://www.python.org/doc/2.5.2/lib/module-array.html" rel="noreferrer"> حدة.

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 قد يكون أسرع في بعض الأجهزة، ولكن من المشكوك فيه.]

Answer 5

ولقد طرح تنفيذ مرشح الثعبان ازهر في HTTP: // سترومبرغ .dnsalias.org / ~ strombrg / DRS-ازهر مرشح /

وانها في بيثون النقي، وظائف التجزئة جيدة، واختبارات مؤتمتة جيدة، ومجموعة مختارة من الخلفيات (القرص، مجموعة، mmap، وأكثر) والحجج أكثر بديهية لطريقة __init__، حتى تتمكن من تحديد العدد المثالي من العناصر والمطلوب الحد الأقصى لمعدل الخطأ، بدلا من tunables أثيري إلى حد ما،-بنية بيانات محددة.

Answer 6

وأنا مهتم تماما في بلوم مرشحات المتغيرات، والأداء، وفهم من حالات الاستخدام. هناك الكثير من استشهد جيدا الأبحاث على مرشح المتغيرات بلوم (بما في ذلك تلك التي نشرت في مؤتمرات أرفع مثل SIGCOMM، SIGMETRICS) ولكن أنا لا أعتقد أن وجودها القوي في المكتبات اللغة السائدة. لماذا تعتقد أن هذا هو الحال؟

وعلى الرغم اهتمامي هو على اللغة الملحد، أردت أن حصة مقال كتبته على مرشح المتغيرات بلوم، وتطبيقات فلتر بلوم.

http://appolo85.wordpress.com/2010/08/ 03 / ازهر مرشح /

وأنا أحب لمعرفة المزيد عن استعمالها-حالات التصفية المتغيرات بلوم، وتصميمها / تنفيذ والمكتبات في لغات أخرى.

هل تعتقد أن معظم المنشورات، و(رمز؟) على بلوم مرشحات المتغيرات، لا تؤدي إلا إلى زيادة عدد رقة نشرت خريج الدكتوراه منتديات ام ان معظم الناس لا يريدون الفوضى مع معيار تنفيذ مرشح ازهر جاهزة للإنتاج أن "يعمل على ما يرام": D