خوارزميات البحث وآلية عملها

سوف نستعرض في هذه المقالة خوارِزميتان من خوارزميات البحث الشهيرة، وهما خوارزمية البحث الثنائي، وخوارزمية البحث الخطي، مع تحليلهما وشرح آلية عملهما.

البحث الثنائي Binary Search

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

تبدأ خوارزمية البحث الثنائي في كل خطوة بالتحقق من القيمة الموجودة في منتصف المصفوفة mid، فإن كانت تساوي العنصر المبحوث عنه فإنها تتوقف وتعيد فهرسه؛ وإلا تقسّم المصفوفة إلى اثنتين هما مصفوفة [mid,b] ومصفوفة [a,mid]، حيث يمثل a و b طرفي المصفوفة.

وإن كان العنصر المبحوث عنه موجودا في المصفوفة وكان أكبر من mid، فهذا يعني أنّه سيكون لا محالة في الجزء [mid,b] لأنّ المصفوفة مرتبة؛ أما إذا كان العنصر المبحوث عنه أصغر من mid فهذا يعني أنّه سيكون في الجزء [a,mid].

نختار الآن الجزء المناسب، ونعيد تطبيق الخوارزمية عليه، ونستمر في هذه العملية إلى أن نجد العنصر المبحوث عنه أو تتساوى قيمة mid مع قيمة a، فإن لم تكن قيمة mid تساوي العنصر المبحوث، فهذا يعني أنّه غير موجود في المصفوفة.

إليك مثالًا توضيحيًا؛ لنفترض أنّك خبير اقتصادي وقد تمّ تكليفك بمهمة تحديد سعر التوازن equilibrium price (أي السعر الذي يحقق المعادلة العرض = الطلب) لسلعة الأرز. تذكّر أنه كلما زاد السعر، زاد العرض وقلّ الطلب.

لنفترضّ أنّ الشركة التي تعمل فيها توفر لك جميع المعطيات المتعلقة بالعرض والطلب المتعلقين بالأرز عندما يستقر سعر الأرز عند قيمة معيّنة ‎p‎، فعندئذ تستطيع الحصول على العرض والطلب بوحدات الأرز. ويريد رئيسك أن تحسب سعر التوازن في أسرع وقت ممكن، لكن سينبّهك إلى أنّ سعر التوازن يجب أن يكون عددًا صحيحًا موجبًا لا يتجاوز ‎10^17‎، كما انّه يضمن لك أنّه سيكون هناك حل عددي صحيح موجب واحد بالضبط في هذا النطاق.

يُسمح لك باستدعاء الدالتين ‎getSupply(k)‎ و ‎getDemand(k)‎، وَاللتان تعيدان كمية العرض وحجم الطلب بالنسبة للسعر K على التوالي.

المبحث أو مساحة البحث هنا هي مصفوفة الأعداد الصحيحة من ‎1‎ إلى ‎10^17‎. ويكون البحث الخطي في هذه الحالة غير مناسب لأنّ المصفوفة مرتّبة. لاحظ أنه كلما ارتفعت قيمة ‎k‎، ستزيد قيمة ‎getSupply(k)‎، وتنخفض قيمة ‎getDemand(k)‎، ومن ثم تكون لدينا المتراجحة التالية:

اقتباس

لكل ‎x > y‎ لدينا: getSupply(x) - getDemand(x) > getSupply(y) - getDemand(y)‎‎

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

المثال التوضيحي التالي يبين كيفية استخدام خوارزمية البحث الثنائي:

high = 100000000000000000     <- الحد الأقصى لمساحة المبحث
low = 1                       <-  الحد الأدنى لمساحة المبحث
while high - low > 1
   mid = (high + low) / 2    <- خذ القيمة الوسطى
   supply = getSupply(mid) 
   demand = getDemand(mid)
   if supply > demand       
       high = mid             <- الحل موجود في النصف السفلي من مساحة المبحث
   else if demand > supply
       low = mid              <- الحل موجود في النصف العلوي من مساحة المبحث
   else                       <- الشرط: العرض == الطلب
       return mid             <- العثور على الحل

تستغرق هذه الخوارزمية وقتًا مقداره ‎~O(log 10^17)‎. وعمومًا، يساوي تعقيد خوارزمية الترتيب الثنائي ‎~O(log S)‎، حيث يمثّل S حجم مصفوفة البحث، لأنّنا نقلّص مساحة البحث إلى النصف في كل تكرار للحلقة while، (من [low: high] إلى [low: mid] أو [mid: high] ).

فيما يلي تطبيق على خوارزمية البحث الثنائي يستخدم التكرارية، في لغة ?

int binsearch(int a[], int x, int low, int high) {
   int mid;
   if (low > high)
     return -1;
   mid = (low + high) / 2;
   if (x == a[mid]) {
       return (mid);
   } else
   if (x < a[mid]) {
       binsearch(a, x, low, mid - 1);
   } else {
       binsearch(a, x, mid + 1, high);
   }
}

خوارزمية رابِن كارب Rabin Karp

خوارزمية رابِن كارب هي خوارزمية بحث نصية تستخدم دالة تعمية hashing للعثور على نمط معيّن من مجموعة من الأنماط النصية في سلسلة نصية، ومتوسط أوقات تشغيلها وأفضلها يساوي المدة O(n + m)‎‎ في المساحة (O(p، حيث يمثّل n طول السلسلة النصية، فيما يمثّل m طول النمط. بالمقابل، فأسوأ أوقات تشغيلها يساوي O(nm)‎‎.

هذا تطبيق لخوارزمية مطابقة السلاسل النصية في لغة جافا، حيث يمثل q عددًا أوليًا، و p يمثل قيمة التجزئة الخاصة بالنمط، و t قيمة التجزئة الخاصة بالنص، و d يمثل عدد الحروف الأبجدية.

void RabinfindPattern(String text,String pattern){
   int d=128;
   int q=100;
   int n=text.length();
   int m=pattern.length();
   int t=0,p=0;
   int h=1;
   int i,j;
//دالة حساب قيمة التجزئة
   for (i=0;i<m-1;i++)
           h = (h*d)%q;
       for (i=0;i<m;i++){
       p = (d*p + pattern.charAt(i))%q;
       t = (d*t + text.charAt(i))%q;
       }
// البحث عن النمط
   for(i=0;i<end-m;i++){
       if(p==t){
// إن تطابقت قيمة التجزئة، فقارن النمط حرفا حرفا
           for(j=0;j<m;j++)
               if(text.charAt(j+i)!=pattern.charAt(j))
               break;
           if(j==m && i>=start)
               System.out.println("Pattern match found at index "+i);           
       }
       if(i<end-m){
           t =(d*(t - text.charAt(i)*h) + text.charAt(i+m))%q;
           if(t<0)
               t=t+q;
       }   
   }                               
}

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

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

t =(d*(t - text.charAt(i)*h) + text.charAt(i+m))%q;

تحليل الحالات التعقيدية لخوارزمية البحث الخطي

كل خوارزمية لها ثلاث حالات تعقيد:

أسوأ حالة.
الحالة المتوسطة.
أفضل حالة.

#include <stdio.h>
// ‫البحث عن x في arr[]‎‎، في حال العثور على x، تعيد الدالة الفهرس
// وإلا أعِد -1
int search(int arr[], int n, int x)
{
   int i;
   for (i=0; i<n; i++)
   {
       if (arr[i] == x)
        return i;
   }
   return -1;
}

برنامج مشغِّل لاختبار الدوال أعلاه:

int main()
{
 int arr[] = {1, 10, 30, 15};
 int x = 30;
 int n = sizeof(arr)/sizeof(arr[0]);
 printf("%d is present at index %d", x, search(arr, n, x));
 getchar();
 return 0;

تحليل أسوأ حالة

عند تحليل الحالة الأسوأ نحسب الحد الأعلى لوقت تشغيل الخوارزمية، ويجب أن نعرف الحالة التي تجعل الخوارزمية تنفّذ أقصى عدد من العمليات. وبالنسبة لخوارزمية البحث الخطي، تحدث أسوأ حالة عندما لا يكون العنصر المبحوث عنه (x) موجودًا في المصفوفة، فحينئذ سوف تقارنه دالة البحث search()‎‎ مع جميع عناصر المصفوفة المبحوث فيها واحدًا تلو الآخر. وعليه، فإنّ أسوأ حالة تعقيدية في خوارزمية البحث الخطي تساوي ‎Θ‎(n)‎‎.

تحليل الحالة التعقيدية المتوسطة

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

لنفترض أنّ جميع الحالات مُوزّعة توزيعًا منتظمًا uniformly distributed -بما في ذلك الحالات التي لا يكون فيها x ضمن المصفوفة-، ثم نجمع جميع تلك الحالات ونقسّم المجموع على (n +1).

هذه صيغة الحالة التعقيدية المتوسطة:

تحليل أفضل حالة

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

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

في بعض الخوارزميات، تكون جميع الحالات متماثلة تقريبًا، إذ لا توجد حالة أسوأ وحالة فضلى، نجد هذا على سبيل المثال في خوارزمية الترتيب بالدمج، إذ ينفّذ الترتيب بالدمج عدد ‎Θ‎(nLogn)‎ عملية في جميع الحالات.

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

تطبيق خوارزمية البحث الثنائي على أعداد مرتبة

هذا مثال توضيحي لتطبيق خوارزمية البحث الثنائي على الأعداد:

int array[1000] = { sorted list of numbers };
int N = 100;  // عدد المدخلات في مساحة المبحث
int high, low, mid; // قيم مؤقتة
int x; // القيمة المبحوث عنها
low = 0;
high = N -1;
while(low < high)
{
   mid = (low + high)/2;
   if(array[mid] < x)
       low = mid + 1;
   else
       high = mid; 
} 
if(array[low] == x)
   // low العثور على العنصر عند الفهرس
else
   // لم نعثر على العنصر

لا تحاول العودة مبكرًا بموازنة العنصر الأوسط array[mid]‎‎ بـ x، فذلك سيضيف عملية موازنة زائدة تبطئ الخوارزمية. لاحظ أن عليك إضافة 1 إلى قيمة low لتجنب أن يُقرّب ناتج القسمة الصحيحة إلى أسفل rounding down.

يتيح الإصدار أعلاه من البحث الثنائي إمكانية إيجاد أصغر فهرس لظهور x في المصفوفة في حال كانت تحتوي عدة نسخ من x، ويمكن تعديل الخوارزمية لجعلها تعيد أكبر فهرس كما تبيّن الشيفرة التالية:

while(low < high)
   {
       mid = low + ((high - low) / 2);
       if(array[mid] < x || (array[mid] == x && array[mid + 1] == x))
           low = mid + 1;
       else
           high = mid; 
   }

لاحظ أنه بدلًا من إجراء العملية التالية:

‎mid = (low + high) / 2‎

فقد يكون الأفضل إجراء العملية الآتية:

‎mid = low + ((high - low) / 2)‎

في التطبيقات التي تستهدف لغات مثل Java لتقليل خطر حصول طفح overﬂow في حال كانت المدخلات كبيرة الحجم.

البحث الخطي linear search

البحث الخطي هي خوارزمية بسيطة، فهي تمرّ على جميع عناصر المصفوفة حتى تعثر على العنصر المبحوث عنه.

تعقيد هذه الخوارزمية يساوي O(n)‎‎، حيث يمثّل n عدد العناصر. قد تسأل لماذا O(n)‎‎؟ لأنّه في أسوأ حالة، سيكون عليك المرور على جميع عناصر المصفوفة، أي على n عنصر.

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

هذا تطبيق لخوارزمية البحث الخطي بلغة بايثون:

def linear_search(searchable_list, query):
   for x in searchable_list:
       if query == x:
           return True
   return False
linear_search(['apple', 'banana', 'carrot', 'fig', 'garlic'], 'fig') #returns True