الجمع بين مرشحات بلوم

Question

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

def combine(a : bloom_filter, b : bloom_filter):
    assert a.length == b.length
    assert a.hashes == b.hashes

    c = new bloom_filter(length = a.length, hashes = b.hashes)
    c.attempts = a.attempts + b.attempts
    c.bits = a.bits | b.bits

    # Determining the amount of items
    a_and_b = count(a & b)
    a_not_b = count(a & !b)
    not_a_b = count(!a & b)
    neither = count(!a & !b)
    c.item_count = a_not_b / a.length * a.item_count
                 + not_a_b / b.length * b.item_count
                 + a_and_b / c.length * min(a.item_count, b.item_count)

    return c

هل هذا يبدو حتى صحيح؟أواجه جدلًا داخليًا كبيرًا حول ما إذا كان من الممكن فعل ما أنويه، نظرًا لفقد الكثير من المعلومات حول البيانات المصدر (وهذا هو الهدف من مرشح الازدهار).

Answer 1

يمكنك استخلاص صيغة لتقدير كمية العناصر مرشح بلوم:

giveacodicetagpre.

يوفر هذا تقديرا دقيقا إلى حد ما لعدد العناصر في مرشح Bloom.يمكنك التوصل إلى تقدير للمساهمة بالطرح البسيط.

Answer 2

قد يكون من الممكن.....نوعا ما..

لنفترض أن المجموعة أ تحتوي على تفاح وبرتقال

لنفترض أن المجموعة ب تحتوي على البازلاء والجزر

أنشئ مرشحًا بسيطًا بلوم 16 بت كمثال وCRC32 كالتجزئة

crc32(apples) = 0x70CCB02F

crc32(oranges) = 0x45CDF3B4

crc32(peas) = 0xB18D0C2B

crc32(carrots) = 0x676A9E28

ابدأ بمرشح إزهار فارغ (BF) (على سبيل المثال 16 بت) لكلا المجموعتين (A، B)

BFA = BFB = 0000 0000 0000 0000 

بعد ذلك ، كسر التجزئة إلى بعض البت ، سنستخدم 4 هنا يمكننا إضافة تفاح إلى BF.على سبيل المثال

Get Apples BF Index list by splitting up the hash:

0x70CCB02F = 0111 0000 1100 1100 1011 0000 0010 1111
             7      0    C    C   B     0    2     F     
----------------------------------------------------

Add Apples to BFA by setting BF bit indexes [ 7, 0, 12, 12, 11, 0, 2, 15]

                                 (set the index bit of an empty BF to 1)
Apples =     1001 1000 1000 0101 (<- see indexes 0,2,7,11,12,15 are set)
BF =         0000 0000 0000 0000  (or operation adds that item to the BF)
================================
Updated BFA = 1001 1000 1000 0101 

أضف البرتقال إلى BF بنفس الطريقة:

0x45CDF3B4 = 0100 0101 1100 1101 1111 0011 1011 0100
              4    5    12   13   15    3   11   4
----------------------------------------------------
Add oranges to BF by setting BF bit indexes [ 4,5,12,13,15,3,11,4]

Oranges =      1011 1000 0011 1000 
BFA =          1001 1000 1000 0101  (or operation)
================================
Updated BFA =  1011 1000 1011 1101 

حتى الآن يتم إدراج التفاح والبرتقال في BF1 ث/ القيمة النهائية 1011 1000 1011 1101

افعل نفس الشيء بالنسبة لـ BFB

crc32(peas) = 0xB18D0C2B becomes => 
set [11,2,12,0,13,1,8] in BFB
 0011 1001 0000 0011 = BF(peas)

crc32(carrots) = 0x676A9E28 becomes => 
set [8,2,14,9,10,6,7] in BFB

0100 0111 1100 0100 = BF(carrots)

so BFB = 
0011 1001 0000 0011  BF(peas)
0100 0111 1100 0100  BF(carrots)
===================  ('add' them to BFB via locial or op)
0111 1111 1100 0111

يمكنك الآن البحث عن B عن إدخالات A في الحلقة والعكس:

هل يحتوي B على "برتقال" =>

 1011 1000 0011 1000 (Oranges BF representation)
 0111 1111 1100 0111 (BFB)
=====================     (and operation)
 0011 1000 0000 0000  

لأن هذه النتيجة (0011 1000 0000 0000) لا يتطابق مع BF الأصلي للبرتقال ، يمكنك أن تكون على يقين من أن B لا يحتوي على أي برتقال

......(افعل لبقية العناصر)

وما يلي ، لا يحتوي B على أي من العناصر ، تمامًا كما لا يحتوي B على أي من التفاح.

لا أعتقد أن هذا ما طلبته رغم ذلك ، ويبدو أنك تستطيع كمبيوتر الفرق BF ، وهو أكثر من ذلك.يبدو أنه يمكنك إجراء عملية xor op وهذا من شأنه أن يمنحك مصفوفة "مفردة" تحتوي على كلا الاختلافين:

0111 1111 1100 0111 (BFB)
1011 1000 1011 1101 (BFA)
========================
1100 0111 0111 1010 (BFA xor BFB) == (items in B not in A, and items in A not in B)

وهذا يعني مع هذا BF الفردي ، يمكنك اكتشاف عدم وجود عنصر 100 ٪ من الوقت ، وليس فقط وجود البند 100 ٪.

الطريقة التي ستستخدمها هي كما يلي (تحقق مما إذا كانت البازلاء مفقودة من A):

 1100 0111 0111 1010 (BFA xor BFB)
 0011 1001 0000 0011 (Peas)
============================== (And operation)
 0000 0001 0000 0010 (non-zero)

منذ (BFA xor BFB) && (Peas) != 0 أنت تعلم أن مجموعة واحدة لا تحتوي على "البازلاء" ...

مرة أخرى، ستختبر عنصرًا تلو الآخر، ربما يمكنك القيام بالتجميع ولكن ربما ليست فكرة جيدة ...

أتمنى أن يساعدك هذا!