خوارزمية رايتا

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

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

وصف

تبحث خوارزمية رايتا عن نمط "P" في نص معين "T" من خلال مقارنة كل حرف من النمط في النص المعطى. ويتم البحث على النحو التالي: تُعرَّف نافذة النص "T" بطول "P".

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

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

توجد صيغة حديثة لفحص مسبق مماثل في std::string::findأداة مطابقة السلاسل الخطية/التربيعية، الموجودة في مكتبتي libc++ و libstdc++. وبافتراض وجود نسخة مُحسَّنة جيدًا من هذه الأداة memcmp، فإن عدم تخطي الأحرف في "المقارنة الأصلية" يميل إلى أن يكون أكثر كفاءة، حيث من المرجح أن يكون النمط مُحاذيًا. [ 2 ]

كود C لخوارزمية رايتا

#include <limits.h> #include <stddef.h>#define ALPHABET_SIZE (1 << CHAR_BITS) /* عادةً 256 *//* المعالجة المسبقة: جدول التطابقات غير الصحيحة لـ BMH. */ static inline void preBmBc ( char * pat , size_t lpat , ptrdiff_t bmBc []) { size_t i ; for ( i = 0 ; i < ALPHABET_SIZE ; ++ i ) bmBc [ i ] = lpat ; for ( i = 0 ; i < lpat - 1 ; ++ i ) bmBc [ pat [ i ]] = lpat - i - 1 ; }void RAITA ( char * pat , size_t lpat , char * s , size_t n ) { ptrdiff_t bmBc [ ALPHABET_SIZE ];/* حالات استثنائية سريعة. */ إذا كان ( lpat == 0 || lpat > n ) فارجع ؛إذا كان ( lpat == 1 ) { char * match_ptr = s ; while ( match_ptr < s + n ) { match_ptr = memchr ( match_ptr , pat [ 0 ], n - ( match_ptr - s )); if ( match_ptr != NULL ) { OUTPUT ( match_ptr - s ); match_ptr ++ ; } else return ; } }preBmBc ( بات ، lpat ، bmBc )؛/* نافذة ما قبل المباراة. */ char firstCh = pat [ 0 ]; char middleCh = pat [ lpat / 2 ]; char lastCh = pat [ lpat - 1 ];/* البحث */ ptrdiff_t j = 0 ; while ( j <= n - m ) { char c = s [ j + lpat - 1 ]; /* قد يؤثر هذا سلبًا على موضع البيانات في الأنماط الطويلة. في هذه الحالة، يُنصح بتقليل  عدد الاختبارات المسبقة، أو استخدام فهارس أكثر تجميعًا. */ if ( lastCh == c && middleCh == s [ j + lpat / 2 ] && firstCh == s [ j ] && memcmp ( & pat [ 1 ], & s [ j + 1 ], lpat - 2 ) == 0 ) OUTPUT ( j ); j ​​+= bmBc [ c ]; } }

مثال

النمط: abddb

النص: abbaabaabddbabadbb

مرحلة المعالجة المسبقة:

 عبد 4 3 1
المحاولة الأولى: abbaabaabddbabadbb ...ب إزاحة بمقدار 4 (bmBc[a])

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

المحاولة الثانية: abbaabaabddbabadbb AdB إزاحة بمقدار 3 (bmBc[b])

هنا، يتطابق الحرف الأخير والأول من النمط، بينما لا يتطابق الحرف الأوسط. لذا، يتم تغيير موضع النمط وفقًا لمرحلة المعالجة المسبقة.

المحاولة الثالثة: abbaabaabddbabadbb ABDDB إزاحة بمقدار 3 (bmBc[b])

لقد وجدنا تطابقًا تامًا هنا، لكن الخوارزمية تستمر حتى لا تتمكن من المضي قدمًا.

المحاولة الرابعة: abbaabaABDDBabadbb ...ب إزاحة بمقدار 4 (bmBc[a])

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

تعقيد

  1. تستغرق مرحلة المعالجة المسبقة O(m) من الوقت حيث "m" هو طول النمط "P".
  2. تستغرق مرحلة البحث تعقيدًا زمنيًا قدره O(mn) حيث "n" هو طول النص "T".

انظر أيضاً

مراجع

  1. 1 2 رايتا ت.، 1992، ضبط خوارزمية البحث عن السلاسل بوير-مور-هورسبول، البرمجيات - الممارسة والخبرة، 22(10):879-884
  2. ↑ "⚙ D27068 تحسين دالة string::find" . مراجعة كود LLVM .