الفصل 4: خوارزميات البحث

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

جداول الرموز وهياكل البيانات

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

• المترجمات، حيث تُستخدم جداول الرموز لتخزين معلومات عن المتغيرات والدوال وغيرها من المعرفات.
• قواعد البيانات، حيث يتم بناء الفهارس باستخدام جداول الرموز لتمكين البحث السريع واسترجاع السجلات.
• موجهات الشبكة، التي تستخدم جداول الرموز لتخزين معلومات التوجيه لتمكين التوجيه الفعال للحزم.

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

أشجار البحث الثنائية (BSTs)

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

فيما يلي مثال على BST بسيط:

      4
    /   \
   2     6
  / \   / \
 1   3 5   7

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

الإدراج في BST يتبع عملية مماثلة للبحث. نقارن مفتاح العقدة الجديدة مع المفاتيح في BST ونتجول في الشجرة حتى نجد مرجعًا فارغًا، حيث نرفق العقدة الجديدة كورقة. الحذف في BST أكثر تعقيدًا قليلاً، حيث يتطلب التعامل مع ثلاث حالات: حذف عقدة ورقة، وحذف عقدة ذات طفل واحد، وحذف عقدة ذات طفلين.

معدل الحالة المتوسطة للزمن المعقد للبحث والإدراج والحذف في BST هو O(log n)، حيث n هو عدد العقد في الشجرة. ومع ذلك، في أسوأ الحالات (على سبيل المثال، عندما يتحول BST إلى قائمة مرتبطة)، تصبح معقدية الوقت O(n). للتخفيف من هذه المشكلة، يمكننا استخدام BSTs المتوازنة ذاتيًا، مثل أشجار AVL أو أشجار الأحمر والأسود، والتي تحافظ على هيكل شجرة شبه متوازن وتضمن أداءً O(log n) في أسوأ الحالات لجميع العمليات.

جداول التجزئة

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

عندما يحدث تصادم، هناك طريقتان رئيسيتان لحله:

1. السلسلة المنفصلة: يتم تنفيذ كل حصة كقائمة مرتبطة.هنا ترجمة الملف إلى اللغة العربية. بالنسبة للرموز البرمجية، لم يتم ترجمة الرموز، وتمت ترجمة التعليقات فقط:

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

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

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

+---+    +-------+
| 0 |--->| (1,A) |
+---+    +-------+
| 1 |--->| (5,B) |---->| (9,C) |
+---+    +-------+     +-------+
| 2 |
+---+
| 3 |--->| (7,D) |
+---+    +-------+
| 4 |
+---+

في هذا المثال، تتطابق المفاتيح 1 و5 و9 مع الحوض 1، لذلك يتم تخزينها في قائمة ربط مرتبطة بذلك الحوض. المفتاح 7 يتطابق مع الحوض 3، وهو الزوج الوحيد المفتاح-القيمة في ذلك الحوض.

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

أشجار البحث المتوازنة

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

أشجار AVL

شجرة AVL، والتي تحمل اسم مخترعيها Adelson-Velsky و Landis، هي شجرة بحث ثنائية متوازنة ذاتيًا حيث تختلف أطوال الأشجار الفرعية اليسرى واليمنى لأي عقدة بمقدار واحد على الأكثر. هذا الاختلاف في الارتفاعهنا هو الترجمة العربية للملف:

يُسمى عامل التوازن. عندما تنتهك عملية الإدراج أو الحذف خاصية AVL (أي أن عامل التوازن يصبح أكبر من 1 أو أقل من -1)، يتم إعادة توازن الشجرة من خلال دوران واحد أو أكثر.

هناك أربعة أنواع من الدوران المستخدمة لإعادة توازن أشجار AVL:

1. الدوران إلى اليسار: يتم إجراؤه عندما يكون عامل التوازن لعقدة أكبر من 1 وعامل توازن طفلها الأيمن غير سالب.

2. الدوران إلى اليمين: يتم إجراؤه عندما يكون عامل التوازن لعقدة أقل من -1 وعامل توازن طفلها الأيسر غير موجب.

3. الدوران إلى اليسار-اليمين: يتم إجراؤه عندما يكون عامل التوازن لعقدة أكبر من 1 وعامل توازن طفلها الأيمن سالب.

4. الدوران إلى اليمين-اليسار: يتم إجراؤه عندما يكون عامل التوازن لعقدة أقل من -1 وعامل توازن طفلها الأيسر موجب.

من خلال الحفاظ على خاصية AVL، تضمن أشجار AVL سوء الحالة الزمنية O(log n) للبحث والإدراج والحذف. ومع ذلك، فإن العوامل الثابتة المشاركة في عمليات شجرة AVL أعلى قليلاً مقارنة بأشجار البحث الثنائية العادية بسبب الحمل الإضافي للحفاظ على عوامل التوازن وإجراء الدوران.

أشجار الأحمر والأسود

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

1. العقدة الجذر دائمًا سوداء.
2. جميع العقد الورقية (NIL) سوداء.
3. إذا كانت العقدة حمراء، فإن كلا طفليها سوداوان.
4. كل مسار من عقدة إلى أي من عقد أوراقها المتفرعة عنها يحتوي على نفس عدد العقد السوداء.

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

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

عمليات البحث التطبيقية

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

قواعد البيانات واسترجاع المعلومات

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

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

تصميم المترجم

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

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

• محاذاة التسلسل: تُستخدم خوارزميات مثل BLAST (أداة البحث عن المحاذاة المحلية الأساسية) وسميث-واترمان لبحث عن أوجه التشابه بين تسلسلات الحمض النووي أو الحمض النووي الريبوزي أو تسلسلات البروتين. تستخدم هذه الخوارزميات تقنيات بحث مختلفة للعثور بكفاءة على أفضل المطابقات بين التسلسلات، مما يساعد الباحثين على تحديد العلاقات التطورية والتشابهات الوظيفية والطفرات المحتملة.

• تجميع الجينوم: تُستخدم خوارزميات البحث لتحديد التداخلات بين قطع الحمض النووي القصيرة (القراءات) التي تم إنشاؤها بواسطة أجهزة التسلسل، مما يسمح بإعادة بناء تسلسل الجينوم الأصلي. يُعد البحث الفعال أمرًا أساسيًا لمعالجة الكميات الهائلة من البيانات التي يتم إنشاؤها في مشاريع التسلسل الحديثة.

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

الأمن السيبراني والتشفير

يتم استخدام خوارزميات البحث في مختلف جوانب الأمن السيبراني والتشفير، بما في ذلك:

• اكتشاف التسلل: غالبًا ما تستخدم أنظمة اكتشاف التسلل في الشبكات خوارزميات البحث مثل Aho-Corasick أو Boyer-Moore لمطابقة أنماط حركة المرور في الشبكة بكفاءة مع قاعدة بيانات من توقيعات الهجمات المعروفة. يسمح هذا بالكشف والوقاية في الوقت الفعلي من التهديدات الأمنية.

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

• التحليل الكريبتوغرافي: في علم التشفير، يتم استخدام خوارزميات البحث لتحليل وقد تستغل نقاط الضعف في أنظمة التشفير. على سبيل المثال، يتم استخدام خوارزميات مثل خطوة عملاق خطوة صغيرة أو رو لبولارد لحل مشكلة اللوغاريتم المنفصل، والتي تقف وراء أمن بعض أنظمة التشفير.

الخاتمة

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

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

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