مطابقة الأنماط ثنائية الأبعاد

في علوم الحاسوب ، تُعرف مطابقة الأنماط ثنائية الأبعاد بأنها مشكلة تحديد مواقع ظهور مصفوفة ثنائية الأبعاد من الأحرف ("النمط") في مصفوفة ثنائية الأبعاد أكبر ("الصورة"، أو قياسًا على البحث عن السلاسل النصية ، "النص"). ^{[ 1 ]}

بافتراض وجود نمط معين${\displaystyle P[m\times m]}$ونص${\displaystyle T[n\times n]}$، أين${\displaystyle m\leq n}$أبسط طريقة هي مقارنة P بكل مصفوفة فرعية بحجم${\displaystyle m\times m}$في T. يبلغ وقت أسوأ حالة لهذه الخوارزمية .${\displaystyle \Theta ((n-m+1)^{2}m^{2})}$يُفترض عادةً أن${\displaystyle m\leq n/2}$ومن ثم يمكن كتابة ذلك على النحو التالي${\displaystyle \Theta (n^{2}m^{2})}$.

سنوضح حلاً أكثر كفاءة (يعود الفضل فيه أساساً إلى بيرد 1977 ) من خلال مثال. لنفترض أن لدينا النمط والنص التاليين

 أبااب أبا بااااب P = bab T = abaab أبا باباب أبابا

نقوم أولاً بإنشاء آلة أهو-كوراسيك للبحث في نص خطي عن حالات ظهور أعمدة P. وكنتيجة ثانوية، نحصل على معرف لكل عمود، بحيث يحصل عمودان متطابقان على نفس المعرف: في مثالنا، لنفترض أن العمود الأول (والثالث) يتم تعريفهما بالرقم 0، والعمود الأوسط بالرقم 1.

بعد ذلك، نقوم بتشغيل الآلة على أعمدة T، فنحصل (في وقت خطي) على مؤشر كلما ظهر أحد أعمدة P في T: في مثالنا، ستكون هذه مصفوفة C بحجم 3×5 كما يلي (يشير الرمز "-" إلى عدم وجود تطابق):

 أبااب أبا بااااب P = bab T = abaaa C = 01--- أبا باباب 10-1 أبابا 010-0

نستخدم الآن خوارزمية كنوت-موريس-برات للبحث في صفوف المصفوفة C عن نمط مطابق للنمط P، أي 010. عندما نجد نمطًا مطابقًا، نكون قد حددنا ظهور النمط P في المصفوفة T. تجدر الإشارة إلى أنه ليس من الضروري الاحتفاظ بكل المصفوفة C، أو كل المصفوفة T، في الذاكرة؛ إذ يمكن قراءة المصفوفة T صفًا صفًا، ومن المصفوفة C يكفي الاحتفاظ بصف واحد فقط في الذاكرة، بالإضافة إلى صف من حالات آلة أهو-كوراسيك وآلة KMP.

زمن تشغيل هذه الخوارزمية هو${\displaystyle O(n^{2})}$إذا تجاهلنا الاعتماد على حجم الأبجدية، وهو أمر موجود في خوارزمية أهو-كوراسيك. مع الأخذ في الاعتبار ذلك، فإن التعقيد هو${\displaystyle O(n^{2}\log k)}$حيث k هو حجم الأبجدية.

تم التخلص من الاعتماد على حجم الأبجدية بواسطة${\displaystyle O(n^{2})}$خوارزمية جليل وبارك . ^{[ 2 ]}​

• خوارزمية البحث عن السلاسل النصية

• أبوستوليكو، ألبرتو (1999). "الفصل 13: مطابقة الأنماط العامة". في عطا الله (محرر). دليل الخوارزميات ونظرية الحوسبة . مطبعة سي آر سي. الصفحات 13-11 . ISBN  0849326494.
• بيرد، ريتشارد س. (1977). "مطابقة الأنماط ثنائية الأبعاد". رسائل معالجة المعلومات . 6 (5): 168-170 .
• جاليل، تسفي؛ بارك، كونسو (1996). "حساب الشاهد ثنائي الأبعاد المستقل عن الأبجدية". مجلة SIAM للحوسبة . 25 (5): 907-935 .