خوارزمية مطابقة السلسلة الساذجة في Python: أمثلة ، مميزة ، إيجابيات وسلبيات

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

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

خوارزمية البحث عن الأنماط الساذجة

في البحث البسيط عن نمط السلسلة ، يختبر البرنامج موضع نمط الإدخال P [1 …… i] في سلسلة من الأحرف T [1… ..m].

لاحظ أن طول نص الإدخال أو السلسلة سيكون دائمًا أكبر من أو يساوي طول النمط.

إليك خوارزمية البحث عن الأنماط الساذجة للغات البرمجة المختلفة.

يبدأ

بات = حجم النمط

str = حجم السلسلة

من أجل i = 0 إلى (str - pat) ، افعل

ل j = 0 بات ، افعل

إذا كان النص [i + j] ≠ نمط [j] ، إذن

كسر الحلقة

منجز

إذا كان j == pat ، إذن

عرض موقف أنا كما تم العثور على نمط

منجز

نهاية

تعد هذه الخوارزمية مهمة جدًا في علوم الكمبيوتر ، حيث تساعد في تقديم نتائج البحث كإخراج.

اقرأ: أنواع خوارزميات الذكاء الاصطناعي التي يجب أن تعرفها

أمثلة لمطابقة السلسلة الساذجة في بايثون

فيما يلي مثال حيث يتم استخدام أسلوب البحث عن الأنماط الساذجة في كود الثعبان.

# برنامج Python لمطابقة السلسلة الساذجة

# خوارزمية البحث

البحث def (P، T):

X = لين (ف)

ص = لين (تي)

# A حلقة للتبديل P [] واحدًا تلو الآخر * /

بالنسبة لـ i في النطاق (X - Y + 1):

ي = 0

# لفهرس i الحالي ، تحقق

# لمطابقة النمط * /

لـ j في النطاق (0 ، X):

إذا (txt [i + j]! = P [j]):

استراحة

إذا (j == X - 1):

طباعة ("تم العثور على نقش في الموضع" ، i)

# كود السائق

إذا كان __name__ == '__main__':

T = "UPGRADEDUBUPGRAABUPGRADEDU"

P = "ترقية"

بحث (P، T)

الإخراج :

تم العثور على نمط في الموضع 0

تم العثور على نمط في الموضع 17

شرح: المركز الأول هو المركز 0 . نظرًا لأن النموذج "UPGRAD" قد تم رصده هنا لأول مرة ، أظهر الناتج أن النمط موجود في الموضع 0.

وبالمثل ، تم العثور على النمط التالي في الموضع 17.

أفضل حالة للبحث عن الأنماط الساذجة

لا يوجد سوى أفضل حالة واحدة لخوارزمية البحث عن الأنماط الساذجة ، على عكس أسوأ حالتين.

تحدث أفضل حالة عندما لا يكون الحرف الأول في نص النمط في أي مكان في سلسلة الإدخال.

مثال:

T [] = "UPGRADEDUHIJKLUPGRA" ؛

P [] = "TUPGRA" ؛

وبالتالي ، فإن عدد حالات أنماط المطابقة هو O (n).

أسوأ حالة للبحث عن الأنماط الساذجة

هناك نوعان من أسوأ الحالات في نهج البحث عن السلسلة الساذجة.

1. عندما تكون جميع الأحرف في النمط مماثلة لتلك الموجودة في سلسلة الإدخال.

T [] = "EEEEEEEEEEEEEEEE" ؛

P [] = "EEE" ؛

1. عندما يختلف الحرف الأخير فقط في النمط عن سلسلة الإدخال.

T [] = "EEEEEEEEEEED" ؛

P [] = "EEEED" ؛

في مثل هذه الحالات ، يكون عدد المقارنات في O (m * (n-m + 1)).

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

تهدف خوارزمية مطابقة السلسلة إلى إيجاد جميع تكرارات نمط معين في النص.

فيما يلي أهم ميزات الخوارزمية.

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

اقرأ أيضًا: هيكل البيانات والخوارزمية في بايثون

مزايا البحث عن الأنماط الساذجة

1. لا توجد مراحل معالجة مسبقة مطلوبة في نهج البحث البسيط ، حيث أن وقت تشغيله يساوي وقت المطابقة.
2. لا توجد مساحة تشغيل إضافية مطلوبة.
3. يمكن إجراء مقارنات الأنماط مع السلاسل بأي ترتيب.

عيوب مطابقة السلسلة الساذجة

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

خاتمة

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

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

إذا كنت مهتمًا بمعرفة المزيد عن الذكاء الاصطناعي والتعلم الآلي ، فراجع IIIT-B & upGrad's دبلوم PG في التعلم الآلي والذكاء الاصطناعي المصمم للمهنيين العاملين ويقدم أكثر من 450 ساعة من التدريب الصارم ، وأكثر من 30 دراسة حالة ومهمة ، حالة خريجي IIIT-B ، أكثر من 5 مشاريع تكميلية عملية ومساعدة وظيفية مع أفضل الشركات.