كيفية تعيين إخراج دالة التجزئة لمؤشرات بلومفيلتر؟

Question

هل يمكن لأي شخص مساعدتي من خلال تقديم مخطط تفصيلي حول كيفية تعيين مخرجات دالة التجزئة لمؤشرات مرشح الازدهار؟هنا لمحة عامة عن com.bloomfilters.

Answer 1

مخطط تفصيلي لكيفية تعيين مخرجات دالة التجزئة إلى مؤشرات مرشح الازدهار

لكل من ك وظائف التجزئة المستخدمة، يتم تعيينها على جزء صغير في مرشح الازدهار تمامًا كما يتم تعيين التجزئة على دلاء التجزئة في جدول التجزئة.لذلك، من الشائع جدًا أن تقول أن دالة التجزئة تولد أعدادًا صحيحة 32 بت، ثم تستخدم المعامل % عامل للحصول على مؤشر قليلا 0 << i < n أين n هو عدد البتات في مرشح الإزهار الخاص بك.

لجعل هذا الأمر ملموسًا للغاية، لنفترض أن دالة التجزئة تولد أرقامًا من 0 إلى 2^32-1، وهناك 1000 بت في مرشح الازدهار الخاص بك:

int bit_index = hash_function(input_value) % 1000;

من المهم أن نلاحظ هنا أن 2^32-1 أكبر بكثير من 1000.لنفترض أن وظيفة التجزئة قامت بدلاً من ذلك بإنشاء أرقام موزعة بشكل متساوٍ ولكن فقط بين 0 و1023 ضمناً، ثم بعد عملية المعامل سيكون من المرجح أن يكون bit_index في النطاق 0..23 مقارنةً بـ 24..999 (لأنه على سبيل المثاليؤدي كل من المدخلات 2 و1002 إلى قيمة ما بعد المعامل 2، ولكن المدخلات 25 فقط تنتج مخرجات 25).لهذا السبب، إذا كانت لديك دالة تجزئة تولد 32 بت، فقد ترغب في استخدام مرشح بلوم بحجم عدد من البتات يعادل قوة اثنين، ثم قم بتقسيم أجزاء من قيمة التجزئة لاستخدامها كما لو كانت وظائف تجزئة مستقلة - كل ذلك موضح في مقالة ويكيبيديا التي تربطها.يتطلب ذلك وظيفة تجزئة ذات نوعية جيدة، حيث سيتم تمرير أي عيوب "تجميعية" في وظيفة التجزئة إلى المخرجات بشكل كامل؛يعد الحصول على عدد أولي من البتات إحدى الطرق للتخفيف من هذا التجزئة الضعيفة.ومع ذلك، مع وظائف التجزئة الجيدة، فإن قوى اثنين تسهل أيضًا استخراج مؤشرات البت باستخدام عمليات البت AND - وإذا لزم الأمر - تحويل البتات، والذي يمكن أن يكون أسرع من معامل الأعداد الصحيحة، على الرغم من أن وظائف التجزئة من المحتمل أن تتضاءل هذا الاعتبار في ملف الأداء العام.

تحرير - معالجة التعليقات...

بافتراض أن وظيفة MD5 الخاصة بك تقوم بإرجاع ملف unsigned char* "ع" ل MD5_DIGEST_LENGTH بايت من البيانات، أقترح عليك أن تجرب:

BOOST_STATIC_ASSERT(MD5_DIGEST_LENGTH >= sizeof(int));
int bit_index = *reinterpret_cast<unsigned int*>(p) % num_of_bloom_filter_bits;

كان ذلك في الواقع فكرة سيئة بشكل خاص - آسف - سأشرح السببين بعد قليل.أولا، للإجابة على سؤالك حول ما يفعله: BOOST_STATIC_ASSERT() تم تصميمه ليعطيك خطأ في الترجمة إذا تم تقييم التعبير الذي تم تمريره إليه false.هنا، إنها في الأساس طريقة لتوثيق متطلبات ذلك MD5_DIGEST_LENGTH - وهو الحجم بالأحرف للتمثيل النصي لتجزئة MD5 - يكون على الأقل مساويًا لعدد البايتات التي يستخدمها نظامك لـ int نوع عدد صحيح.(من المحتمل أن يكون هذا الحجم 4 بايت، ولكن قد يكون 8 بايت.) يهدف هذا المتطلب إلى التأكد من أن reinterpret_cast في السطر التالي آمن.ما يفعله ذلك هو قراءة قيمة من البايتات في بداية التمثيل النصي لتجزئة MD5 كما لو كانت تلك البايتات تحتوي على int.لذا، قل الخاص بك int مقاس يكون 4، تجزئة MD5 هي "0cc175b9c0f1b6a831c399e269772661" كما في تعليقك:تحتوي أول 4 بايتات على "0cc1".رموز ASCII لهذا النص هي 48، 99، 99، 49 عشري.عندما يتم قراءتها في int, ، اعتمادًا على نهاية وحدة المعالجة المركزية، يمكن أن تختلف القيمة، ولكن في الأساس ستحصل على أحد هذه الأرقام مضروبًا في 256^3 بالإضافة إلى رقم آخر في 256^2 بالإضافة إلى رقم ثالث في 256 بالإضافة إلى الرقم النهائي.

الأسباب التي جعلتني أقول إن هذه فكرة سيئة بشكل خاص هي:

• كل حرف في سلسلة MD5 هو إما رقم (رموز ASCII 48-57) أو حرف من "a" إلى "f" (97-102).هذه القيم الـ 16 هي جزء من 16 من التباين الذي يمكن أن يحتوي عليه البايت، وبينما int القيمة التي تنشئها تشغل 32 بت، وتحصل في الواقع على 2^16 قيمة مميزة فقط.
• على بعض أجهزة الكمبيوتر، intيجب محاذاة s على عنوان الذاكرة الذي يكون من مضاعفات 2، 4، 8 وما إلى ذلك.ال reinterpret_cast - إذا بدأ النص بعنوان غير متوافق، فقد يؤدي ذلك إلى تعطل جهاز الكمبيوتر الخاص بك.ملحوظة:ليس لدى Intel وAMD متطلبات المحاذاة هذه، على الرغم من أنه قد يكون من الأسرع بالنسبة لهم العمل على البيانات المحاذاة بشكل صحيح.

إذن اقتراح آخر:

// create a buffer of the right size to hold a valid unsigned long in hex representation...
char data[sizeof(unsigned long) * 2 + 1];

// copy as much of the md5 text as will fit into the buffer, NUL terminating it...
sprintf(data, "%.*s", sizeof data - 1, md5);

// convert to an unsigned long...
m = strtoul(data, /*endptr*/ NULL, /*base*/ 16);

هنا، إذا كان تمثيل md5 أقصر من المخزن المؤقت للبيانات، فسيتم نسخ الجزء الأولي منه بأمان، لذا فإن BOOST_STATIC_ASSERT غير مطلوب.

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