خوارزمية بوير مور
تعتمد خوارزمية بوير-مور Boyer-Moore على أسلوبين أساسيين هما:
- استكشاف الحروف السيئة Bad Character Heuristic
- استكشاف اللاحقة الجيدة Good Suffix Heuristic
يمكن استخدام كل أسلوب من هذين الأسلوبين على حدة للبحث عن نمط في نص معين.
تجري خوارزمية بوير-مور معالجة مسبقة على النمط المراد البحث عنه وذلك لتحريك النمط أثناء عملية المقارنة أكثر من خطوة واحدة. تصنع خوارزمية بوير-مور مصفوفتين مختلفتين لكلا الأسلوبين. وفي كل خطوة من خطوات مطابقة النمط مع النص، تحرك الخوارزمية النمط بمقدار يساوي أعلى قيمة للتحريك يقترحها الأسلوبان الآنفا الذكر.
تبدأ خوارزمية بوير-مور بالمطابقة من آخر حرف في النمط وذلك على عكس بقية خوارزميات البحث عن الأنماط.
استكشاف الحروف السيئة
يعتمد هذا الأسلوب على فكرة بسيطة مفادها أنّ الحرف في النص والذي لا يطابق الحرف الحالي في النمط يسمّى بالحرف السيء Bad Character. وعند حدوث حالة عدم التطابق، فإنّنا نزيح النمط إلى أن يتحقق أحد الأمرين التاليين:
- تتحول حالة عدم التطابق إلى حالة تطابق.
- يتخطّى النمط P الحرف غير المطابق.
الحالة الأولى: تحول حالة عدم التطابق إلى حالة تطابق
يجري البحث في هذه الحالة عن موقع آخر ظهور للحرف غير المطابق في النمط، وإذا كان الحرف غير المطابق موجودًا في النمط فسنزيح النمط بطريقة تجعله محاذيًا للحرف غير المطابق في النص T.
يعرض الشكل التالي مثالًا عن هذه الحالة:
هناك حالة عدم تطابق في الموقع 3، والحرف غير المطابق هنا هو "A". سيجري البحث عن آخر ظهور للحرف "A" في النمط، وهو الموقع 1 في النمط (باللون الأزرق) وهو كذلك آخر ظهور لهذا الحرف في النمط؛ لذا سنحرّك النمط مرتين وذلك لمحاذاة الحرف "A" في النمط مع الحرف "A" في النص.
الحالة الثانية: تخطي النمط للحرف غير المطابق
يجري البحث في هذه الحالة عن موقع آخر ظهور للحرف غير المطابق في النمط، وإن لم يكن الحرف موجودًا يُزاح النمط ليتخطّى الحرف غير المطابق.
يعرض الشكل التالي مثالًا عن هذه الحالة:
هناك حالة عدم تطابق في الموقع 7، والحرف غير المطابق هو الحرف "C" وهو غير موجود في النمط قبل الموقع 7؛ لذا سيزاح النمط ليتخطّى الموقع 7، وستظهر حالة تطابق تام في المثال أعلاه (اللون الأخضر). لاحظ أنّه لمّا كان الحرف "C" غائبًا عن النمط المراد البحث عنه فإنّ أي إزاحة للنمط قبل الموقع 7 ستؤدي إلى الحصول على حالة عدم تطابق وستكون عملية البحث دون فائدة.
تنفيذ الخوارزمية
تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:
- C++:
#include <bits/stdc++.h>
using namespace std;
# define NO_OF_CHARS 256
// دالة المعالجة القبلية لخوارزمية بوير-مور
// بالاعتماد على أسلوب استكشاف الحروف السيئة
void badCharHeuristic( string str, int size,
int badchar[NO_OF_CHARS])
{
int i;
// تهيئة جميع قيم ظهور الحروف لتكون -1
for (i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;
// تعبئة القيمة الحقيقية لآخر ظهور للحرف
for (i = 0; i < size; i++)
badchar[(int) str[i]] = i;
}
/* دالة البحث عن النمط والتي تستخدم أسلوب
استكشاف الحروف السيئة في خوارزمية بوير-مور*/
void search( string txt, string pat)
{
int m = pat.size();
int n = txt.size();
int badchar[NO_OF_CHARS];
/* تعبئة مصفوفة الحروف السيئة وذلك باستدعاء
دالة المعالجة القبلية على النمط المعطى*/
badCharHeuristic(pat, m, badchar);
int s = 0; // مقدار إزاحة النمط بالنسبة إلى النص
while(s <= (n - m))
{
int j = m - 1;
/* j الاستمرار في إنقاص الموقع
في النمط ما دامت حروف النمط وحروف النص
متطابقة في هذه الإزاحة */
while(j >= 0 && pat[j] == txt[s + j])
j--;
/* إن كان النمط موجودًا في الإزاحة الحالية
j فهذا يعني أن الموقع
سيصبح -1 بعد هذه الحلقة */
if (j < 0)
{
cout << "pattern occurs at shift = " << s << endl;
/* إزاحة النمط ليحاذي الحرف التالي في النص
آخر ظهور له في النمط. نحتاج إلى استخدام الشرط
s+m < n
وذلك في حالة ظهور النمط في نهاية النص */
s += (s + m < n)? m-badchar[txt[s + m]] : 1;
}
else
/* إزاحة النمط ليحاذي الحرف السيئ آخر ظهور له
max في النمط. تستخدم الدالة
لضمان الحصول على إزاحة بقيمة موجبة. إذ يمكن الحصول
على إزاحة بقيمة سالبة إن كان آخر ظهور للحرف السيئ
في النمط على الجهة اليمنى من الحرف الحالي */
s += max(1, j - badchar[txt[s + j]]);
}
}
/* اختبار الدوال السابقة */
int main()
{
string txt= "ABAAABCD";
string pat = "ABC";
search(txt, pat);
return 0;
}
- بايثون:
NO_OF_CHARS = 256
def badCharHeuristic(string, size):
'''
دالة المعالجة القبلية لخوارزمية بوير-مور
بالاعتماد على أسلوب استكشاف الحروف السيئة
'''
# تهيئة جميع قيم ظهور الحروف لتكون -1
badChar = [-1]*NO_OF_CHARS
# تعبئة القيمة الحقيقية لآخر ظهور للحرف
for i in range(size):
badChar[ord(string[i])] = i;
# إعادة القائمة المهيئة
return badChar
def search(txt, pat):
'''
دالة البحث عن النمط والتي تستخدم أسلوب
استكشاف الحروف السيئة في خوارزمية بوير-مور
'''
m = len(pat)
n = len(txt)
# تعبئة مصفوفة الحروف السيئة وذلك باستدعاء
# دالة المعالجة القبلية على النمط المعطى
badChar = badCharHeuristic(pat, m)
# مقدار إزاحة النمط بالنسبة إلى النص
s = 0
while(s <= n-m):
j = m-1
# j الاستمرار في إنقاص الموقع
# في النمط ما دامت حروف النمط وحروف النص
# متطابقة في هذه الإزاحة
while j>=0 and pat[j] == txt[s+j]:
j -= 1
# إن كان النمط موجودًا في الإزاحة الحالية
# j فهذا يعني أن الموقع
# سيصبح -1 بعد هذه الحلقة
if j<0:
print("Pattern occur at shift = {}".format(s))
'''
إزاحة النمط ليحاذي الحرف التالي في النص
آخر ظهور له في النمط. نحتاج إلى استخدام الشرط
s+m < n
وذلك في حالة ظهور النمط في نهاية النص
'''
s += (m-badChar[ord(txt[s+m])] if s+m<n else 1)
else:
'''
إزاحة النمط ليحاذي الحرف السيئ آخر ظهور له
max في النمط. تستخدم الدالة
لضمان الحصول على إزاحة بقيمة موجبة. إذ يمكن الحصول
على إزاحة بقيمة سالبة إن كان آخر ظهور للحرف السيئ
في النمط على الجهة اليمنى من الحرف الحالي
'''
s += max(1, j-badChar[ord(txt[s+j])])
# اختبار الدوال السابقة
def main():
txt = "ABAAABCD"
pat = "ABC"
search(txt, pat)
if __name__ == '__main__':
main()
- جافا:
class AWQ{
static int NO_OF_CHARS = 256;
// دالة مساعدة للحصول على العدد الأكبر من بين عددين
static int max (int a, int b) { return (a > b)? a: b; }
// دالة المعالجة القبلية لخوارزمية بوير-مور
// بالاعتماد على أسلوب استكشاف الحروف السيئة
static void badCharHeuristic( char []str, int size,int badchar[])
{
int i;
// تهيئة جميع قيم ظهور الحروف لتكون -1
for (i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;
// تعبئة القيمة الحقيقية لآخر ظهور للحرف
for (i = 0; i < size; i++)
badchar[(int) str[i]] = i;
}
/* دالة البحث عن النمط والتي تستخدم أسلوب
استكشاف الحروف السيئة في خوارزمية بوير-مور*/
static void search( char txt[], char pat[])
{
int m = pat.length;
int n = txt.length;
int badchar[] = new int[NO_OF_CHARS];
/* تعبئة مصفوفة الحروف السيئة وذلك باستدعاء
دالة المعالجة القبلية على النمط المعطى*/
badCharHeuristic(pat, m, badchar);
int s = 0; // مقدار إزاحة النمط بالنسبة إلى النص
while(s <= (n - m))
{
int j = m-1;
/* j الاستمرار في إنقاص الموقع
في النمط ما دامت حروف النمط وحروف النص
متطابقة في هذه الإزاحة */
while(j >= 0 && pat[j] == txt[s+j])
j--;
/* إن كان النمط موجودًا في الإزاحة الحالية
j فهذا يعني أن الموقع
سيصبح -1 بعد هذه الحلقة */
if (j < 0)
{
System.out.println("Patterns occur at shift = " + s);
/* إزاحة النمط ليحاذي الحرف التالي في النص
آخر ظهور له في النمط. نحتاج إلى استخدام الشرط
s+m < n
وذلك في حالة ظهور النمط في نهاية النص */
s += (s+m < n)? m-badchar[txt[s+m]] : 1;
}
else
/* إزاحة النمط ليحاذي الحرف السيئ آخر ظهور له
max في النمط. تستخدم الدالة
لضمان الحصول على إزاحة بقيمة موجبة. إذ يمكن الحصول
على إزاحة بقيمة سالبة إن كان آخر ظهور للحرف السيئ
في النمط على الجهة اليمنى من الحرف الحالي */
s += max(1, j - badchar[txt[s+j]]);
}
}
/* اختبار الدوال السابقة */
public static void main(String []args) {
char txt[] = "ABAAABCD".toCharArray();
char pat[] = "ABC".toCharArray();
search(txt, pat);
}
}
التعقيد الزمني
تجري طريقة التنفيذ أعلاه معالجة قبلية للنمط وتخزّن آخر ظهور لكل حرف ممكن في مصفوفة حجمها مساوٍ لعدد الحروف الأبجدية. إن لم يكن الحرف موجودًا إطلاقًا، فإنّ هذا سيؤدي إلى إزاحة النمط بمقدار m (طول النمط)، وبهذا يبلغ التعقيد الزمني لأسلوب استكشاف الحروف السيئة المقدار O(n/m) في أفضل الحالات.
ولكن قد يبلغ التعقيد الزمني لهذا الأسلوب المقدار O(mn) في أسوأ الحالات والتي تكون فيها حروف النص والنمط متطابقة بالكامل، مثل: txt[] = "AAAAAAAAAAAAAAAAAAA" وpat[] = "AAAAA".
استكشاف اللاحقة الجيدة
لنفترض وجود سلسلة نصية t متفرعة من النصّ T والذي تجري مطابقته بواسطة سلسلة نصية متفرّعة من النمط P، ففي أسلوب الاستكشاف هذا نزيح النمط إلى أن تتحق إحدى الحالات التالية:
- تطابق ظهورٍ آخر للسلسلة النصية
tفي النمطPمع السلسلة النصيةtفي النصّT. - تطابق سابقة في
Pمع لاحقة منtفي النصّT. - تخطّي
Pللسلسلة النصيةt.
الحالة الأولى: تطابق ظهورٍ آخر للسلسلة النصية t في النمط P مع السلسلة النصية t في النصّ T.
قد يحتوي النمط P على حالات ظهور أخرى للسلسلة النصية t، وفي مثل هذه الحالة سنحاول إزاحة النمط لمحاذاة حالة الظهور تلك مع السلسلة النصية t في النص T. فعلى سبيل المثال:
توجد في المثال أعلاه سلسلة نصية t متفرّعة من النصّ T متطابقة مع النمط P (اللون الأخضر) قبل حالة عدم التطابق في الموقع 2. سنبحث الآن عن ظهور للسلسلة النصية t (وهي "AB") في النمط P. وقد وجدنا ظهورًا يبدأ من الموقع 1 (الخلفية الصفراء) لذا سنزيح النمط إلى اليمين مرتين لمحاذاة t في P مع t في T. هذه الطريقة ليست فعالة وسنعرض طريقة أخرى أكثر قوة فيما يلي.
الحالة الثانية: تطابق سابقة في P مع لاحقة من t في النص T
إن احتمال العثور على ظهور للسلسلة النصية t في النمط P ليس احتمالًا قويًا، وفي بعض الأحيان لا تظهر السلسلة النصية في النمط على الإطلاق، وفي مثل هذه الحالات يمكن البحث في بعض الأحيان عن لاحقة في t تطابق سابقة في P ومحاذاتهما معًا عن طريق إزاحة النمط P. فعلى سبيل المثال:
توجد في المثال أعلاه سلسلة نصية t (وهي "BAB") مطابقة للنمط P (اللون الأخضر) في الموقع 2-4 قبل حالة عدم التطابق. ولكن لا وجود لأي ظهور للسلسلة t في النمط P ولذلك سنبحث عن سابقة في النمط P تطابق لاحقة في السلسلة النصية t. ويلاحظ أنّ السابقة "AB" (الخلفية الصفراء) تبدأ من الموقع 0 وتطابق اللاحقة "AB" في السلسلة النصية t في الموقع 3. لذا سنزيح النمط 3 مرات لمحاذاة اللاحقة مع السابقة.
الحالة الثالثة: تخطّي P للسلسلة النصية t
إن لم تتحق الحالتان السابقتان، يُزاح النمط ليتخطّى السلسلة النصّية t، فعلى سبيل المثال:
يلاحظ عدم وجود أيّ ظهور للسلسلة النصية t (وهي "AB") في النمط P، إلى جانب عدم وجود لاحقة في النمط تطابق سابقة في السلسلة النصية t. لهذا، لا يمكن وجود تطابق تام قبل الموقع 4، ويُزاح النمط P ليتخطّى السلسلة النصّية t أي سينتقل النمط إلى الموقع 5.
مصادر
- صفحة Boyer Moore Algorithm for Pattern Searching في توثيق الخوارزميات في موقع GeeksforGeeks.