تتمثل إحدى المسائل الكلاسيكية في العثور على أول ظهور لنمط (Pattern) معين، ولنرمز له بـ P، داخل سلسلة نصية (String)، ولنرمز لها بـ T. وتوجد خوارزميات كلاسيكية متنوعة لحل هذه المسألة بكفاءة، مثل خوارزميات "بوير-مور" (Boyer-Moore) و"كنوث-موريس-برات" (Knuth-Morris-Pratt) و"تو-واي" (Two-Way). أود في هذا المقال استعراض خوارزمية أقل شهرة، وهي خوارزمية "بيتاب" (Bitap) -أو ما يُعرف بـ "شيفت-آند" (Shift-And)- التي تعمل بكفاءة عندما يكون النمط P قصيراً نسبياً (أي أن طوله يقل عن عرض "كلمة الآلة" أو machine word). ورغم ما لهذه الخوارزمية من قيود، إلا أنني أفضلها كثيراً؛ فهي بسيطة الفهم والتطبيق، وتتمتع بكفاءة عالية نسبياً عند التعامل مع السلاسل النصية القصيرة، كما أنها توظف العمليات المنطقية على مستوى البتات (bit operations) بأسلوب أنيق ومميز.
ولإثبات أن هذه الخوارزمية تتسم بالبساطة المفاهيمية المذكورة، سأحاول استنباطها تدريجياً، بدءاً من أبسط خوارزميات مطابقة السلاسل النصية وأكثرها بدائية.
تحويل الخوارزمية البسيطة (الساذجة) إلى خوارزمية تدفق (Streaming)
لنفرض الآن قيداً إضافياً يدفعنا لتعديل الخوارزمية قليلاً: بدلاً من الحصول على جميع محارف النص $T$ دفعة واحدة، لنفترض أنها تُقدَّم الآن على شكل تدفق بيانات، بحيث يصل محرف واحد في كل مرة (ربما يكون النص $T$ طويلاً جداً ولا نرغب في تحميل كامل محتوياته في الذاكرة دفعة واحدة).
الخوارزمية البسيطة المذكورة أعلاه لا تعمل بنظام التدفق؛ فهي تحتاج إلى قراءة ما يصل إلى $m = \text{len}(P)$ من المحارف المتقدمة (أي التي تلي الموقع الحالي) في النص $T$ لاكتشاف مطابقة للنمط $P$. فكيف يمكننا تكييفها بحيث تجري تمريرة واحدة فقط عبر البيانات؟
بعد قليل من التفكير، نتوصل إلى الصيغة التالية المعدلة من خوارزمية البحث الشامل (brute-force). بدلاً من محاولة اكتشاف وجود النمط $P$ فوراً عن طريق القراءة المسبقة في النص $T$ بدءاً من كل موقع $i=0, \dots$، يمكننا الاحتفاظ بمجموعة من المطابقات "قيد التنفيذ" أثناء مسح النص $T$. من الناحية المفاهيمية، تتكون المطابقة قيد التنفيذ من بادئة (prefix) النمط $P$ التي طُوبقت بالفعل قبل الموقع الحالي، بالإضافة إلى اللاحقة (suffix) المتبقية التي لم تُطابق بعد. وعند قراءة محرف جديد $c$ في النص $T$، نقوم بتقديم المطابقات التي تنتظر هذا المحرف $c$، ونلغي (أو ننهي) بقية المطابقات. وإذا وصلت أي من المطابقات النشطة إلى نهاية النمط $P$، نكون قد أتممنا المهمة.
ليست هناك تعليقات:
إرسال تعليق