تُستخدم مطابقة الأنماط على نطاق واسع في علوم الكمبيوتر والعديد من المجالات الأخرى. تُستخدم خوارزميات مطابقة الأنماط للبحث عن الأنماط داخل نص أكبر أو مجموعة بيانات. إحدى الخوارزميات الأكثر شيوعًا لمطابقة الأنماط هي بوير مور الخوارزمية، والتي تم نشرها لأول مرة في عام 1977. في هذه المقالة، سنناقش خوارزميات مطابقة الأنماط في لغة C وكيفية عملها.
ما هي خوارزمية مطابقة الأنماط؟
تُستخدم خوارزميات مطابقة الأنماط للعثور على الأنماط ضمن مجموعة أكبر من البيانات أو النصوص. تعمل هذه الخوارزميات من خلال مقارنة النمط بمجموعة بيانات أو نص أكبر وتحديد ما إذا كان النمط موجودًا أم لا. تعد خوارزميات مطابقة الأنماط مهمة لأنها تتيح لنا البحث عن الأنماط في مجموعات البيانات الكبيرة بسرعة.
قم بتشغيل جافا
خوارزمية مطابقة نمط القوة الغاشمة:
تعد مطابقة أنماط القوة الغاشمة أبسط خوارزمية لمطابقة الأنماط. يتضمن مقارنة أحرف النمط مع أحرف النص واحدة تلو الأخرى. إذا تطابقت جميع الأحرف، تقوم الخوارزمية بإرجاع موضع بداية النمط في النص. إذا لم يكن الأمر كذلك، تنتقل الخوارزمية إلى الموضع التالي في النص وتكرر المقارنة حتى يتم العثور على تطابق أو الوصول إلى نهاية النص. التعقيد الزمني لخوارزمية القوة الغاشمة أو(MXN) ، أين م يدل على طول النص و ن يدل على طول النموذج.
خوارزمية مطابقة الأنماط الساذجة:
تعد خوارزمية مطابقة الأنماط الساذجة بمثابة تحسين على خوارزمية القوة الغاشمة. إنه يتجنب المقارنات غير الضرورية عن طريق تخطي بعض المواضع في النص. تبدأ الخوارزمية بمقارنة النمط بالنص الموجود في الموضع الأول. إذا تطابقت الأحرف، فإنه ينتقل إلى الموضع التالي ويكرر المقارنة. إذا لم تتطابق الأحرف، تنتقل الخوارزمية إلى الموضع التالي في النص وتقارن النمط بالنص مرة أخرى. التعقيد الزمني للخوارزمية الساذجة هو أيضًا أو(MXN) ولكنها أسرع من خوارزمية Brute Force في معظم الحالات.
خوارزمية نوث-موريس-برات:
ال نوث موريس برات (KMP) الخوارزمية هي خوارزمية أكثر تقدمًا لمطابقة الأنماط. ويستند إلى ملاحظة أنه عند حدوث عدم تطابق، يمكن استخدام بعض المعلومات حول النص والنمط لتجنب المقارنات غير الضرورية. تقوم الخوارزمية بحساب جدول يحتوي على معلومات حول النمط مسبقًا. يحدد الجدول عدد أحرف النموذج التي يمكن تخطيها عند حدوث عدم تطابق. التعقيد الزمني لل كمب الخوارزمية هي يا (م + ن) .
خوارزمية بوير-مور:
إحدى خوارزميات مطابقة الأنماط الأكثر شيوعًا هي بوير مور خوارزمية. تم نشر هذه الخوارزمية لأول مرة في عام 1977 من قبل روبرت س. بوير وج ستروثر مور. ال بوير مور تقارن الخوارزمية نمطًا مع مجموعة أكبر من البيانات أو النص من اليمين إلى اليسار بدلاً من اليسار إلى اليمين، كما هو الحال مع معظم خوارزميات مطابقة الأنماط الأخرى.
ال بوير مور تحتوي الخوارزمية على مكونين رئيسيين: قاعدة الشخصية السيئة وقاعدة اللاحقة الجيدة. تعمل قاعدة الأحرف السيئة من خلال مقارنة الحرف الموجود في النمط بالحرف المقابل في البيانات أو النص. إذا كانت الأحرف غير متطابقة، تقوم الخوارزمية بنقل النمط إلى اليمين حتى تجد الحرف المطابق. تقارن قاعدة اللاحقة الجيدة لاحقة النموذج مع اللاحقة المقابلة للبيانات أو النص. إذا كانت اللواحق غير متطابقة، تقوم الخوارزمية بنقل النمط إلى اليمين حتى تجد لاحقة مطابقة.
ال بوير مور تُعرف الخوارزمية بكفاءتها وتستخدم على نطاق واسع في العديد من التطبيقات. تعتبر واحدة من أسرع خوارزميات مطابقة الأنماط المتاحة.
تنفيذ خوارزمية Boyer-Moore في لغة C:
لتنفيذ بوير مور الخوارزمية في لغة C، يمكننا أن نبدأ بتحديد قاعدة الأحرف السيئة. يمكننا استخدام مصفوفة لتخزين آخر تواجد لكل حرف في النمط. يمكن لهذه المصفوفة تحديد المدى الذي يجب أن ننقل فيه النموذج إلى اليمين عند حدوث عدم تطابق.
فيما يلي مثال لكيفية تنفيذ قاعدة الأحرف السيئة في لغة C:
نسخة جافا لينكس
كود ج:
void bad_character_rule(char *pattern, int pattern_length, int *bad_char) { int i; for (i = 0; i <no_of_chars; i++) bad_char[i]="-1;" for (i="0;" i < pattern_length; bad_char[(int) pattern[i]]="i;" } pre> <p>In this example, we first initialize the array to -1 for all characters. We then iterate through the pattern and update the array with the last occurrence of each character in the pattern.</p> <p>Next, we can implement the good suffix rule. We can use an array to store the length of the longest suffix of the pattern that matches a suffix of the data or text. This array can be used to determine how far we need to move the pattern to the right.</p> <hr></no_of_chars;>