بناء تومسون

في علم الحاسوب ، تُعرف خوارزمية تومسون الإنشائية ، أو خوارزمية ماكناوتون-يامادا-تومسون ، ^[¹^] بأنها طريقة لتحويل التعبير النمطي إلى آلة حالة منتهية غير حتمية مكافئة (NFA). ^[²^] يمكن استخدام هذه الآلة لمطابقة السلاسل النصية مع التعبير النمطي. يُنسب الفضل في هذه الخوارزمية إلى كين تومسون .

تُعدّ التعابير النمطية والآلات المحدودة غير الحتمية تمثيلين للغات الرسمية . فعلى سبيل المثال، تستخدم برامج معالجة النصوص التعابير النمطية لوصف أنماط البحث المتقدمة، بينما تُعدّ الآلات المحدودة غير الحتمية أكثر ملاءمةً للتنفيذ على الحاسوب. لذا، تُعتبر هذه الخوارزمية ذات أهمية عملية، إذ يمكنها تحويل التعابير النمطية إلى آلات محدودة غير حتمية. ومن الناحية النظرية، تُشكّل هذه الخوارزمية جزءًا من إثبات أن كليهما يقبلان اللغات نفسها تمامًا، أي اللغات النمطية .

يمكن جعل آلة الحالة غير القطعية حتميةً باستخدام بناء مجموعة القوى ، ثم تصغيرها للحصول على آلة مثالية تتوافق مع التعبير النمطي المعطى. مع ذلك، يمكن أيضًا تفسير آلة الحالة غير القطعية مباشرةً .

لتحديد ما إذا كان تعبيران نمطيان معينان يصفان اللغة نفسها، يمكن تحويل كل منهما إلى آلة حتمية محدودة مكافئة باستخدام بناء طومسون، وبناء مجموعة القوى ، وتقليل حجم الآلة الحتمية المحدودة . إذا، وفقط إذا، اتفقت الآلات الناتجة باستثناء إعادة تسمية الحالات، فإن لغات التعبيرين النمطيين تتفق.

الخوارزمية

تعمل الخوارزمية بشكل تكراري عن طريق تقسيم التعبير إلى تعبيراته الفرعية المكونة له، والتي يتم من خلالها بناء آلة الحالة المحدودة غير القطعية (NFA) باستخدام مجموعة من القواعد. ^{[ 3 ]} وبشكل أدق، من تعبير منتظم $E$ ، فإن الآلة $A$ الناتجة ذات دالة الانتقال $Δ$ تحترم الخصائص التالية:

للحالة $A حالة ابتدائية واحدة فقط$ $q 0$ ، وهي غير قابلة للوصول من أي حالة أخرى. أي أنه لأي حالة $q$ وأي حرف $a$ ، $\Delta (q,a)$ لا يحتوي على $q 0$ .
$للحرف A$ حالة نهائية واحدة فقط $q f$ ، وهي حالة لا يمكن الوصول إليها من أي حالة أخرى. أي أنه لأي حرف $a$ ، $\Delta (q_{f},a)=\emptyset$ .
لنفترض أن $c$ هو عدد مرات دمج التعبير النمطي $E،$ ولنفترض أن $s$ هو عدد الرموز باستثناء الأقواس - أي $|$ و $*$ و $a$ و $ε$ . عندئذٍ، يكون عدد حالات $A$ هو $2 s - c$ (وهو عدد خطي يتناسب مع حجم $E$ ).
عدد الانتقالات التي تغادر أي حالة هو اثنان على الأكثر.
بما أن آلة الحالة المحدودة غير القطعية (NFA) المكونة من $m$ حالة وعدد انتقالات لا يتجاوز $e$ من كل حالة يمكنها مطابقة سلسلة طولها $n$ في زمن $O (emn)$ ، فإن آلة الحالة المحدودة غير القطعية من نوع طومسون يمكنها إجراء مطابقة الأنماط في زمن خطي، بافتراض أبجدية ذات حجم ثابت. ^{[ 4 ]}

قواعد

تم توضيح القواعد التالية وفقًا لـ Aho et al. (2007)، ^{[ 1 ]} ص. 122. وفيما يلي، N ( s ) و N ( t ) هما NFA للتعبيرات الفرعية s و t ، على التوالي.

يتم تحويل التعبير الفارغ ε إلى

يتم تحويل الرمز a من الأبجدية المدخلة إلى

يتم تحويل تعبير الاتحاد s | t إلى

تنتقل الحالة q عبر ε إما إلى الحالة الأولية لـ N ( s ) أو N ( t ). تصبح حالاتها النهائية حالات وسيطة لـ NFA بأكملها وتندمج عبر انتقالين ε إلى الحالة النهائية لـ NFA.

يتم تحويل تعبير التسلسل st إلى

الحالة الابتدائية لـ N ( s ) هي الحالة الابتدائية للآلة غير القطعية الكاملة. وتصبح الحالة النهائية لـ N ( s ) هي الحالة الابتدائية لـ N ( t ). والحالة النهائية لـ N ( t ) هي الحالة النهائية للآلة غير القطعية الكاملة.

يتم تحويل تعبير النجمة Kleene s *^إلى

يربط انتقال إبسيلون الحالة الابتدائية والنهائية للآلة غير القطعية المحدودة (NFA) مع الآلة الفرعية N ( s ) بينهما. يسمح انتقال إبسيلون آخر من الحالة النهائية الداخلية إلى الحالة الابتدائية الداخلية للآلة N ( s ) بتكرار التعبير s وفقًا لمؤثر النجمة.

يتم تحويل التعبير بين قوسين ( s ) إلى N ( s ) نفسه.

باستخدام هذه القواعد، وباستخدام قواعد التعبير الفارغ والرمز كحالات أساسية، من الممكن إثبات بالاستقراء البنيوي أنه يمكن تحويل أي تعبير منتظم إلى آلة حالة نهائية غير قطعية مكافئة . ^[¹^]

مثال

نقدم الآن مثالين، أحدهما صغير وغير رسمي مع النتيجة، والآخر أكبر مع تطبيق خطوة بخطوة للخوارزمية.

مثال صغير

مثال على `(ε|a*b)`استخدام طريقة تومسون الإنشائية، خطوة بخطوة

تُظهر الصورة أدناه نتيجة بناء طومسون على (ε|a*b). يتوافق الشكل البيضاوي الأرجواني مع a ، ويتوافق الشكل البيضاوي الفيروزي مع a* ، ويتوافق الشكل البيضاوي الأخضر مع b ، ويتوافق الشكل البيضاوي البرتقالي مع a*b ، ويتوافق الشكل البيضاوي الأزرق مع ε .

تطبيق الخوارزمية

على سبيل المثال، تُظهر الصورة نتيجة خوارزمية بناء طومسون على التعبير النمطي (0|(1(01*(00)*0)*1)*)*الذي يدل على مجموعة الأرقام الثنائية التي هي مضاعفات للعدد 3:

{ ε، "0"، "00"، "11"، "000"، "011"، "110"، "0000"، "0011"، "0110"، "1001"، "1100"، "1111"، "00000"، ... }.

يُظهر الجزء العلوي الأيمن البنية المنطقية (شجرة بناء الجملة) للتعبير، حيث تشير النقطة (.") إلى عملية الربط (بافتراض أن عدد المعاملات متغير)؛ وتُسمى التعبيرات الفرعية من a إلى q لأغراض مرجعية. يُظهر الجزء الأيسر الآلة المحدودة غير الحتمية الناتجة عن خوارزمية طومسون، مع تلوين حالتي الدخول والخروج لكل تعبير فرعي باللونين الأرجواني والسماوي ، على التوالي. تم حذف ε كعلامة انتقال للتوضيح - الانتقالات غير المُسماة هي في الواقع انتقالات ε. حالة الدخول والخروج المقابلة للتعبير الجذري q هي حالتي البداية والقبول للآلة، على التوالي.

خطوات الخوارزمية هي كالتالي:

س :	ابدأ بتحويل تعبير نجمة كلين									`(0\|(1(01(00)0)1))*`
	ب :	بدء تحويل تعبير الاتحاد								`0\|(1(01(00)0)1)`
		أ :	رمز التحويل							`0`
		ص :	ابدأ بتحويل تعبير نجمة كلين							`(1(01(00)0)1)`
			د :	بدء تحويل تعبير التسلسل						`1(01(00)0)*1`
				ج :	رمز التحويل					`1`
				ن :	ابدأ بتحويل تعبير نجمة كلين					`(01(00)0)*`
					f :	بدء تحويل تعبير التسلسل				`01(00)0`
						هـ :	رمز التحويل			`0`
						ح :	ابدأ بتحويل تعبير نجمة كلين			`1*`
							ز :	رمز التحويل		`1`
						ح :	تم الانتهاء من تحويل تعبير نجمة كلين			`1*`
						ل :	ابدأ بتحويل تعبير نجمة كلين			`(00)*`
							ج :	بدء تحويل تعبير التسلسل		`00`
								أنا :	رمز التحويل	`0`
								ك :	رمز التحويل	`0`
							ج :	تم الانتهاء من تحويل تعبير التسلسل		`00`
						ل :	تم الانتهاء من تحويل تعبير نجمة كلين			`(00)*`
						م :	رمز التحويل			`0`
					f :	تم الانتهاء من تحويل تعبير التسلسل				`01(00)0`
				ن :	تم الانتهاء من تحويل تعبير نجمة كلين					`(01(00)0)*`
				o :	رمز التحويل					`1`
			د :	تم الانتهاء من تحويل تعبير التسلسل						`1(01(00)0)*1`
		ص :	تم الانتهاء من تحويل تعبير نجمة كلين							`(1(01(00)0)1)`
	ب :	إنهاء تحويل تعبير الاتحاد								`0\|(1(01(00)0)1)`
س :	تم الانتهاء من تحويل تعبير نجمة كلين									`(0\|(1(01(00)0)1))*`

يظهر أدناه نموذج مكافئ لآلة حتمية دنيا.

العلاقة بالخوارزميات الأخرى

تُعدّ خوارزمية طومسون إحدى الخوارزميات العديدة لبناء آلات الحالة المحدودة غير القطعية (NFAs) من التعابير النمطية؛ ^{[ 5 ]} وقد قدّم ماكناوتون ويامادا خوارزمية سابقة. ^{[ 6 ]} وعلى عكس خوارزمية طومسون، تُحوّل خوارزمية كلين آلة الحالة المحدودة إلى تعبير نمطي.

تتشابه خوارزمية بناء غلوشكوف مع خوارزمية بناء طومسون، بمجرد إزالة انتقالات إبسيلون.

يُستخدم في مطابقة أنماط السلاسل النصية

تُستخدم التعابير النمطية غالبًا لتحديد الأنماط التي يُطلب من البرامج مطابقتها. من خلال إنشاء آلة حالة نهائية غير قطعية (NFA) باستخدام طريقة تومسون، واستخدام خوارزمية مناسبة لمحاكاتها، يُمكن إنشاء برامج مطابقة الأنماط بأداءٍ عالٍ . $O(mn)$ حيث يُمثل m طول التعبير النمطي، و n طول السلسلة المراد مطابقتها. يُعد هذا أفضل بكثير مما تُحققه العديد من تطبيقات لغات البرمجة الشائعة؛^{[ 7 ]} ومع ذلك، فهو يقتصر على التعبيرات النمطية فقط، ولا يدعم أنماط اللغات غير النمطية مثل المراجع الخلفية.

مراجع

1 2 3 ألفريد فاينو أهو ؛ مونيكا س. لام ؛ رافي سيثي ؛ جيفري د. أولمان (2007). "3.7.4 بناء آلة حالة نهائية غير قطعية من تعبير نمطي" (مطبوع) . المترجمات : المبادئ والتقنيات والأدوات (الطبعة الثانية ). بوسطن، ماساتشوستس، الولايات المتحدة الأمريكية: بيرسون أديسون ويسلي. ص 159-163 . ISBN 9780321486813.
↑ لودن، كينيث سي. (1997). "2.4.1 من التعبير النمطي إلى الأوتومات غير القطعي" (مطبوع) . بناء المترجمات : المبادئ والتطبيق ( الطبعة الثالثة). 20 بارك بلازا، بوسطن، ماساتشوستس 02116-4324، الولايات المتحدة الأمريكية: شركة بي دبليو إس للنشر. الصفحات 64-69 . ISBN 978-0-534-93972-4.{{cite book}}: CS1 maint: location ( link )
↑ كين تومسون (يونيو 1968). "تقنيات البرمجة: خوارزمية البحث باستخدام التعبيرات النمطية" . مجلة اتصالات رابطة مكائن الحوسبة . 11 (6): 419-422 . doi : 10.1145/363347.363387 . S2CID 21260384 .
↑ شينغ، غوانغمينغ. "تصغير ثومبسون NFA" (PDF) .
↑ واتسون، بروس و. (1995). تصنيف خوارزميات بناء الأوتوماتا المحدودة (ملف PDF) (تقرير فني). جامعة آيندهوفن للتكنولوجيا . تقرير علوم الحاسوب 93/43.
↑ ر. ماكناوتون، هـ. يامادا (مارس 1960). "التعابير النمطية ومخططات الحالة للأتمتة". معاملات IEEE للحاسبات الإلكترونية . 9 (1): 39-47 . Bibcode : 1960IRTEC...9...39M . doi : 10.1109/TEC.1960.5221603 .
↑ كوكس، روس. "مطابقة التعبيرات النمطية يمكن أن تكون بسيطة وسريعة (لكنها بطيئة في جافا، بيرل، بي إتش بي، بايثون، روبي، ...)" . swtchboard . تم الاطلاع عليه بتاريخ 25 فبراير 2025 .

[DragonBook-1] 1 2 3 ألفريد فاينو أهو ؛ مونيكا س. لام ؛ رافي سيثي ؛ جيفري د. أولمان (2007). "3.7.4 بناء آلة حالة نهائية غير قطعية من تعبير نمطي" (مطبوع) . المترجمات : المبادئ والتقنيات والأدوات (الطبعة الثانية ). بوسطن، ماساتشوستس، الولايات المتحدة الأمريكية: بيرسون أديسون ويسلي. ص 159-163 . ISBN 9780321486813.

[2] لودن، كينيث سي. (1997). "2.4.1 من التعبير النمطي إلى الأوتومات غير القطعي" (مطبوع) . بناء المترجمات : المبادئ والتطبيق ( الطبعة الثالثة). 20 بارك بلازا، بوسطن، ماساتشوستس 02116-4324، الولايات المتحدة الأمريكية: شركة بي دبليو إس للنشر. الصفحات 64-69 . ISBN 978-0-534-93972-4.{{cite book}}: CS1 maint: location ( link )

[3] كين تومسون (يونيو 1968). "تقنيات البرمجة: خوارزمية البحث باستخدام التعبيرات النمطية" . مجلة اتصالات رابطة مكائن الحوسبة . 11 (6): 419-422 . doi : 10.1145/363347.363387 . S2CID 21260384 .

[4] شينغ، غوانغمينغ. "تصغير ثومبسون NFA" (PDF) .

[5] واتسون، بروس و. (1995). تصنيف خوارزميات بناء الأوتوماتا المحدودة (ملف PDF) (تقرير فني). جامعة آيندهوفن للتكنولوجيا . تقرير علوم الحاسوب 93/43.

[6] ر. ماكناوتون، هـ. يامادا (مارس 1960). "التعابير النمطية ومخططات الحالة للأتمتة". معاملات IEEE للحاسبات الإلكترونية . 9 (1): 39-47 . Bibcode : 1960IRTEC...9...39M . doi : 10.1109/TEC.1960.5221603 .

[7] كوكس، روس. "مطابقة التعبيرات النمطية يمكن أن تكون بسيطة وسريعة (لكنها بطيئة في جافا، بيرل، بي إتش بي، بايثون، روبي، ...)" . swtchboard . تم الاطلاع عليه بتاريخ 25 فبراير 2025 .

[

[

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]