كتاب "الخوارزمية المثالية. خوارزميات الرسم البياني وهياكل البيانات "

مرحبا ، habrozhiteli! الخوارزميات هي قلب وروح علوم الكمبيوتر. لا يمكنك الاستغناء عنها ، فهي موجودة في كل مكان - بدءًا من توجيه الشبكة وحسابات الجينوم إلى التشفير والتعلم الآلي. ستحولك "الخوارزمية المثالية" إلى محترف حقيقي سيحدد المهام ويحلها ببراعة في الحياة وفي مقابلة عند التعاقد مع أي شركة لتكنولوجيا المعلومات.

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

يعرض هذا المنشور مقتطفًا من Bloom Filters: The Basics.

ما هو هذا الكتاب عنه

الجزء الثاني من كتاب "الخوارزمية المثالية" هو دورة تمهيدية حول أساسيات محو الأمية في الموضوعات الثلاثة التالية.

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

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

هياكل البيانات . سيجعلك هذا الكتاب مستخدمًا تعليميًا عالي المستوى لعدة هياكل بيانات مختلفة مصممة لدعم مجموعة متطورة من الكائنات باستخدام المفاتيح المرتبطة بها. الهدف الرئيسي هو تطوير حدس حول بنية البيانات المناسبة لتطبيقك. توفر أقسام إضافية إرشادات لتنفيذ هذه الهياكل البيانات من البداية.

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

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

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

12.5. بلوم فلاتر: الأساسيات

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

12.5.1. العمليات المدعومة

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

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

بلوم المرشحات: العمليات المدعومة

عرض: باستخدام المفتاح k ، قم بإرجاع "نعم" إذا تم إدراج k مسبقًا في مرشح Bloom ، و "لا" على خلاف ذلك.
لصق: أضف مفتاحًا جديدًا k إلى مرشح Bloom.

فلاتر بلوم فعالة جدا من الناحية المكانية ؛ عادة ، قد تتطلب فقط 8 بت لكل إدراج. هذا أمر لا يصدق ، حيث أن 8 بتات غير كافية تمامًا لتتذكر حتى مفتاح 32 بت أو مؤشر إلى كائن! لهذا السبب ، فإن عملية العرض في مرشح بلوم تُرجع فقط الإجابة "نعم" / "لا" ، بينما في جدول التجزئة ، تُرجع هذه العملية مؤشرًا إلى الكائن المرغوب (إذا وجد). هذا هو السبب في أن عملية الإدراج تقبل الآن المفتاح فقط ، وليس المؤشر (الكائن).

على عكس جميع هياكل البيانات الأخرى التي درسناها ، يمكن أن تكون عوامل تصفية Bloom خاطئة. هناك نوعان من الأخطاء: السلبيات الخاطئة عندما تُرجع عملية العرض "خطأ" حتى لو تم بالفعل إدراج المفتاح المطلوب مسبقًا ، وبيانات خطأ (أو إيجابيات) عندما تُرجع عملية العرض "صواب" ، على الرغم من أن المفتاح المطلوب لم يتم إدراجه في الماضي . في القسم 12.5.3 ، سنرى أن مرشحات Bloom الأساسية لا تعاني أبدًا من السلبيات الخاطئة ، ولكن يمكن أن تحتوي على "عناصر وهمية" في شكل بيانات خاطئة. يوضح القسم 12.6 أن تواتر الادعاءات الخاطئة يمكن التحكم فيه عن طريق ضبط استخدام الفضاء بشكل مناسب. قد يكون للتطبيق النموذجي لمرشح Bloom معدل خطأ يبلغ حوالي 1٪ أو 0.1٪.

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

لتلخيص مزايا وعيوب عوامل تصفية Bloom على جداول التجزئة:

مرشح بلوم ضد علامات التجزئة

1. الايجابيات: أكثر فعالية من الناحية المكانية.

2. الايجابيات: عمليات مضمونة في الوقت الدائم لكل مجموعة بيانات.

3. سلبيات: لا يمكن تخزين المؤشرات على الأشياء.

4. سلبيات: الحذف أكثر تعقيدا بالمقارنة مع جدول التجزئة مع مخلب.

5. سلبيات: احتمال عدم الصفر لبيان كاذب.

قائمة المؤشرات لمرشحات Bloom الأساسية هي كما يلي.

الجدول 12.4. عوامل تصفية Bloom الأساسية: العمليات المدعومة ووقت تنفيذها. تشير علامة الخنجر (†) إلى أن عملية "العرض" لها احتمال يمكن السيطرة عليه وغير صفري من الادعاءات الخاطئة


يجب استخدام عوامل تصفية Bloom بدلاً من جداول التجزئة في التطبيقات التي تكون فيها مزاياها وعيوبها لا تشكل عقبة أمام المعاملة.

عند استخدام مرشح بلوم

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

12.5.2. تطبيقات

بعد ذلك ، هناك ثلاثة استخدامات مع عمليات مسح متكررة ، حيث يمكن أن يكون توفير مساحة مهمًا ، ولا تشكل البيانات الخاطئة عقبة أمام المعاملة.

المدقق الإملائي. مرة أخرى في 1970s ، تم استخدام مرشحات بلوم لتنفيذ لعبة الداما الإملائي - المدقق الإملائي. في مرحلة ما قبل المعالجة ، يتم إدراج كل كلمة في القاموس في مرشح بلوم. يأتي التدقيق الإملائي للمستند في عملية واحدة ، انظر إلى كلمة في مستند ، مع الإشارة إلى أي كلمات ترجع هذه العملية إلى "لا".

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

كلمات السر المحظورة . يتتبع تطبيق قديم يظل ساري المفعول حتى يومنا هذا كلمات المرور الممنوعة - كلمات المرور شائعة جدًا أو يسهل تخمينها. في البداية ، يتم إدراج جميع كلمات المرور الممنوعة في مرشح Bloom ؛ يمكن إدخال كلمات مرور محظورة إضافية في وقت لاحق ، حسب الحاجة. عندما يحاول المستخدم تعيين كلمة المرور الخاصة به أو إعادة تعيينها ، يبحث النظام عن كلمة المرور المقترحة في مرشح Bloom. إذا تم إرجاع "نعم" ، فسيطلب من المستخدم إعادة المحاولة بكلمة مرور مختلفة. هنا ، يتم ترجمة عبارة خاطئة إلى كلمة مرور قوية ، والتي يرفضها النظام.

بشرط ألا يكون معدل الخطأ مرتفعًا جدًا ، لا تقل عن 1٪ أو 0.1٪ ، فهذا لا يهم كثيرًا. من وقت لآخر ، سيحتاج بعض المستخدمين إلى محاولة إضافية واحدة للعثور على كلمة مرور مقبولة للنظام.

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

12.5.3. تطبيق

عند النظر إلى مرشح Bloom ، يمكنك رؤية تطبيق أنيق. تدعم بنية البيانات سلسلة n-bit ، أو بالمثل ، صفيف A بطول n يكون كل عنصر فيه 0 أو 1. (تتم تهيئة جميع العناصر إلى صفر.) تستخدم هذه البنية أيضًا وظائف m hash h1 ، h2 ، ... ، hm ، بينما يقوم كل مخطط بتخطيط الكون U لجميع المفاتيح الممكنة للمجموعة {0 ، 1 ، 2 ، ... ، n - 1} من المواضع في الصفيف. المعلمة m متناسبة مع عدد البتات التي يستخدمها مرشح Bloom للإدراج ، وكقاعدة عامة ، ثابت صغير (على سبيل المثال ، 5).

عندما يتم إدخال مفتاح في مرشح Bloom ، تقوم كل وظيفة من وظائف m hash بتعيين علامة ، وتعيين البت المقابل للصفيف A إلى 1.

تصفية بلوم: إدراج (على مفتاح)

for i = 1 to m do A[hi(k)] := 1 

على سبيل المثال ، إذا كانت m = 3 و h1 (k) = 23 ، h2 (k) = 17 و h3 (k) = 5 ، فإن إدخال k يؤدي إلى ضبط البتات الخامسة ، 17 و 23 من المصفوفة على قدم المساواة 1 (الشكل 12.5).


في عملية العرض ، يبحث مرشح Bloom عن بصمة الأصابع التي ربما تكون قد بقيت في insert k.

بلوم فلتر: عرض (مفتاح رئيسي)

 for i = 1 to m do if A [hi (k)] = 0 then return «» return «» 

الآن يمكننا أن نرى لماذا مرشحات بلوم لا يمكن أن تعاني من السلبيات الكاذبة. عند إدخال المفتاح k ، يتم ضبط البتات m المقابلة على 1. خلال عمر مرشح Bloom ، يمكن للبت أن تغير قيمتها من 0 إلى 1 ، ولكن ليس العكس. وبالتالي ، تبقى هذه البتات m 1 إلى الأبد. ويضمن كل عملية عرض k اللاحقة لإرجاع الإجابة نعم الصحيحة.

يمكننا أن نرى أيضا كيف تنشأ بيانات خاطئة. افترض أن m = 3 والمفاتيح الأربعة k1 و k2 و k3 و k4 تحتوي على قيم التجزئة التالية:


لنفترض أننا أدخلنا k1 و k2 و k3 و k4 في مرشح Bloom (الشكل 12.6). تؤدي هذه الإضافات الثلاثة إلى تعيين تسع بتات على 1 ، بما في ذلك ثلاث بتات في بصمة المفتاح k1 (5 و 17 و 23). في هذه المرحلة ، لم يعد بإمكان مرشح Bloom تمييز ما إذا كان قد تم إدخال المفتاح k1 أم لا. حتى إذا لم يتم إدراج k1 في الفلتر ، فسوف يُرجع البحث "نعم" ، وهو عبارة خاطئة.

حدسيًا ، يمكننا أن نفترض أنه مع زيادة الحجم n لمرشح Bloom ، يجب تقليل عدد التراكبات بين بصمات المفاتيح المختلفة ، مما يؤدي بدوره إلى عدد أقل من العبارات الخاطئة. ولكن الهدف الأساسي من مرشح بلوم هو توفير مساحة. هل هناك أرضية وسط تكون فيها كل من n ووتيرة التصريحات الخاطئة صغيرة في وقت واحد؟ الجواب غير واضح ويتطلب بعض التحليل الرياضي الذي أجري في القسم التالي.



»يمكن الاطلاع على مزيد من المعلومات حول الكتاب على موقع الناشر
» المحتويات
» مقتطفات

ل Khabrozhiteley خصم 20 ٪ على القسيمة - الخوارزميات
عند دفع النسخة الورقية من الكتاب ، يتم إرسال كتاب إلكتروني عبر البريد الإلكتروني.