بحث الاستيفاء

📅 آخر تحديث: ٣ أغسطس ٢٠٢٦
✍️ نُشر في: ٣ أغسطس ٢٠٢٦
الموسوعة الحرة

البحث بالاستيفاء هو خوارزمية للبحث عن مفتاح في مصفوفة مُرتبة وفقًا لقيم عددية مُخصصة للمفاتيح . وصفها لأول مرة دبليو دبليو بيترسون عام ١٩٥٧. [ ١ ] يُشبه البحث بالاستيفاء طريقة البحث في دليل الهاتف عن اسم (قيمة المفتاح التي تُرتب بها بيانات الدليل): في كل خطوة، تحسب الخوارزمية موقع العنصر المطلوب في مساحة البحث المتبقية، بناءً على قيم المفاتيح عند حدود مساحة البحث وقيمة المفتاح المطلوب، عادةً عبر استيفاء خطي . ثم تُقارن قيمة المفتاح الموجودة فعليًا في هذا الموقع المُقدّر بقيمة المفتاح المطلوب. إذا لم تتطابق القيمتان، يتم تقليص مساحة البحث المتبقية، بناءً على المقارنة، إلى الجزء الذي يسبق أو يلي الموقع المُقدّر. لا تنجح هذه الطريقة إلا إذا كانت حسابات حجم الفروق بين قيم المفاتيح منطقية.

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

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

في البحث التسلسلي بالاستيفاء، يتم استخدام الاستيفاء للعثور على عنصر قريب من العنصر الذي يتم البحث عنه، ثم يتم استخدام البحث الخطي للعثور على العنصر المحدد.

أداء

باستخدام ترميز Big-O ، يكون أداء خوارزمية الاستيفاء على مجموعة بيانات بحجم n هو O ( n )؛ ومع ذلك، بافتراض توزيع منتظم للبيانات على المقياس الخطي المستخدم للاستيفاء، يمكن إثبات أن الأداء هو O (log log n ). [ 3 ] [ 4 ] [ 5 ]

يوسّع البحث الديناميكي بالاستيفاء الحدّ O (log log n ) ليشمل توزيعات أخرى، كما يدعم أيضًا عمليات الإدخال والحذف O (log n ). [ 6 ] [ 7 ]

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

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

التكيف مع مجموعات البيانات المختلفة

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

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

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

البحث القائم على الكتب

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

نموذج للتنفيذ

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

استيراد < cassert > ;استيراد std ؛باستخدام std :: vector ;/*إذا كانت المصفوفة arr[low, high] مرتبة، فابحث عن البيانات "key" في هذه المصفوفة.إذا تم العثور على "المفتاح"، فقم بإرجاع الفهرس المقابل (ليس بالضرورة أعلى فهرس ممكن)؛إذا لم يتم العثور على "المفتاح"، فقم بإرجاع القيمة المنخفضة ناقص 1كيف يمكن التحقق من صحة الخوارزمية؟دليل:(النهائية: بعد حلقة واحدة، يتناقص عرض [منخفض، مرتفع] بشكل صارم)قبضة، عالية <--- عالية - 1السيناريو 1. عندما يكون المستوى المنخفض مساوياً للمستوى المرتفعالسيناريو الثاني: عندما يكون الحد الأدنى < الحد الأعلى، فإن arr[low] = arr[high]السيناريو 3. عندما يكون الحد الأدنى < الحد الأعلى، arr[low] < arr[high]، المفتاح < arr[low] أو المفتاح > arr[high]السيناريو 4. عندما يكون الحد الأدنى < الحد الأعلى، فإن arr[low] < arr[high]، و arr[low] <= key <= arr[high]والآن دعونا نحلل السيناريو الرابع:بمجرد الدخول إلى حلقة "while"، يكون الحد الأدنى أقل من أو يساوي الحد الأوسط أقل من أو يساوي الحد الأعلى. لنحلل بعد دورة واحدة (إذا لم نقم بالعودة)، ما إذا كان سيحدث "منخفض > مرتفع". بعد دورة واحدة: الحالة a1: تم تنفيذ الفرع "المنخفض" في هذه الحلقة arr[middle] < key <= arr[high] إذن لدينا متوسط ​​< عالي إذن بعد هذه الحلقة، لدينا منخفض <= مرتفع الحالة a2: تم تنفيذ الفرع "high" في هذه الحلقة arr[low] <= key < arr[middle] إذن لدينا منخفض < متوسط إذن بعد هذه الحلقة، لدينا منخفض <= مرتفع لذا بعد دورة واحدة (إذا لم نقم بالعودة)، يكون لدينا "المنخفض <= المرتفع" عند الخروج من حلقة "while": الحالة b1: arr[low] >= arr[high] في الحلقة الأخيرة، إذا تم تنفيذ الفرع "المنخفض"، فإننا نعلم arr[low - 1] < k <= arr[high] arr[low] >= arr[high] منخفض <= مرتفع لذلك لدينا arr[low - 1] < k <= arr[low] = arr[high] في الحلقة الأخيرة، إذا تم تنفيذ الفرع "العالي"، فإننا نعلم arr[low] <= key < arr[high + 1] arr[low] >= arr[high] منخفض <= مرتفع لذلك لدينا arr[low] = arr[high] <= key < arr[high + 1] الحالة b2: (arr[low] < arr[high]) && (arr[low] > key): في الحلقة الأخيرة، لا بد أن "low" قد تم تغييره لذلك لدينا arr[low - 1] < key لذلك لدينا arr[low - 1] < key < arr[low] الحالة b3: (arr[low] < arr[high]) && (key > arr[high]) في الحلقة الأخيرة، لا بد أن "high" قد تم تغييرها لذلك لدينا key < arr[high + 1] لذلك لدينا arr[low] < arr[high] < key < arr[high + 1]*/// الإصدار 1قالب < نوع الاسم T >دالة البحث الثابتة Rank interpolationSearch ( vector < T >& arr , const T & key , Rank low , Rank high ) {مرتفع -= 1 ؛int middle ;int initialLow = low ;بينما (( arr [ low ] < arr [ high ]) && ( arr [ low ] <= key ) && ( key <= arr [ high ])) {middle = low + (( key - arr [ low ]) * ( high - low )) / ( arr [ high ] - arr [ low ]);تحقق من أن (( المنخفض <= المتوسط ) و ( المتوسط ​​<= المرتفع ));إذا كان ( arr [ middle ] < key ) {منخفض = متوسط ​​+ 1 ؛} else if ( key < arr [ middle ]) {مرتفع = متوسط ​​- 1 ؛} آخر {أعد المنتصف ؛}}إذا كان ( المفتاح == arr [ low ]) {العودة إلى مستوى منخفض ؛} آخر {أعد القيمة الابتدائية الدنيا ناقص واحد ؛}}/*ابحث عن "المفتاح" في المصفوفة المرتبة arr[low, high)القيمة المُعادة: أعلى فهرس i بحيث يكون arr[i] <= keyكيف يمكن التحقق من صحة الخوارزمية؟دليل:خاصية التناهي: بعد دورة واحدة، يتناقص عرض [منخفض، مرتفع] بشكل صارمقبضة، عالية <---- عالية - 1السيناريو 1. عندما يكون المستوى المنخفض مساوياً للمستوى المرتفعالسيناريو الثاني: عندما يكون الحد الأدنى < الحد الأعلى، يكون المفتاح < arr[low] أو يكون arr[high] <= المفتاحالسيناريو 3. عندما يكون الحد الأدنى < الحد الأعلى، يكون arr[low] <= key < arr[high]والآن دعونا نحلل السيناريو الثالث:بمجرد الدخول إلى حلقة "while"، يكون الحد الأدنى أقل من أو يساوي الحد الأوسط، ويكون الحد الأعلى أقل من أو يساوي الحد الأقصى.عند الخروج من حلقة "while": الحالة a1: المفتاح < arr[low] لذا، تم تغيير قيمة "low" في الحلقة الأخيرة، كما نعلم. arr[low - 1] <= key < arr[low] الحالة a2: arr[high] <= key لذا، تم تغيير قيمة "high" في الحلقة الأخيرة، كما نعلم. المفتاح < arr[high]، مستحيلالخلاصة: يجب أن نعيد "low - 1"*/// الإصدار 2قالب < نوع الاسم T >دالة البحث الثابتة Rank interpolationSearch ( vector < T >& arr , const T & key , Rank low , Rank high ) {مرتفع -= 1 ؛assert ( low <= high );المرتبة المتوسطة ؛إذا كان ( المفتاح < arr [ low ]) {أعد القيمة المنخفضة - 1 ؛}إذا كان ( arr [ high ] <= key ) {العودة إلى مستوى عالٍ ؛}// الآن منخفض < مرتفع، arr[low] <= مفتاح < arr[high]بينما (( arr [ low ] <= key ) && ( key < arr [ high ])) {middle = low + (( high - low ) * ( key - arr [ low ])) / ( arr [ high ] - arr [ low ]);تحقق من أن (( المنخفض <= المتوسط ) و ( المتوسط ​​< المرتفع ));إذا كان ( المفتاح < arr [ الوسط ]) {مرتفع = متوسط ؛} آخر {منخفض = متوسط ​​+ 1 ؛}}أعد القيمة المنخفضة - 1 ؛}

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

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

انظر أيضاً

مراجع

  1. ↑ دبليو دبليو بيترسون (1957). "عنونة التخزين ذي الوصول العشوائي". مجلة آي بي إم للبحوث والتطوير 1 ( 2): 130-146 . doi : 10.1147/rd.12.0130 .
  2. ↑ سيمون يوان. "فهم تعقيد البحث الاستيفائي، ندوة الخوارزميات المتقدمة وهياكل البيانات" (PDF) .
  3. ↑ وايس، مارك ألين (2006). هياكل البيانات وحل المشكلات باستخدام جافا ، بيرسون أديسون ويسلي
  4. ↑ أرميناكيس، أ.س، غاري، ل.إ، غوبتا، ر.د، تكييف طريقة البحث عن الجذر للبحث في ملفات القرص المرتبة، الرياضيات العددية BIT، المجلد 25، العدد 4 / ديسمبر، 1985.
  5. ↑ سيدجويك، روبرت (1990)، الخوارزميات في لغة سي ، أديسون-ويسلي
  6. ↑ ميلهورن، كورت؛ تساكاليديس، أثاناسيوس (1993). "بحث الاستيفاء الديناميكي". مجلة ACM . 40 (3): 621-634 . doi : 10.1145/174130.174139 . ISSN 0004-5411 . 
  7. ↑ أندرسون، آرني؛ ماتسون، كريستر (1993). "بحث الاستيفاء الديناميكي في زمن o(log log n)". الأوتوماتا، واللغات، والبرمجة . المجلد 700. برلين، هايدلبرغ: سبرينغر برلين هايدلبرغ. ص 15-27. doi : 10.1007/3-540-56939-1_58 . ISBN   978-3-540-56939-8.
  8. ↑ محمد، عدنان ساهر؛ عمراهوف، شاهين إمراه؛ تشلبي، فاتح ف. (1 أكتوبر 2021). "البحث الثنائي المُستكمل: خوارزمية بحث هجينة فعّالة على مجموعات البيانات المرتبة" . مجلة العلوم والتكنولوجيا الهندسية . 24 (5): 1072-1079 . doi : 10.1016/j.jestch.2021.02.009 . ISSN 2215-0986 .