خوارزميات بحث سريعة للسلاسل الحرفية

العناوين الأخرى

Fast string searching algorithms

مقدم أطروحة جامعية

الحسنات، أحمد بشير عبد الله

مشرف أطروحة جامعية

عبابنة، إسماعيل محمد

أعضاء اللجنة

العكور، محمد علي أحمد
الربابعة، مأمون
العبادي، محمد علي

الجامعة

جامعة آل البيت

الكلية

كلية الأمير الحسين بن عبد الله لتكنولوجيا المعلومات

القسم الأكاديمي

قسم علوم الحاسوب

دولة الجامعة

الأردن

الدرجة العلمية

ماجستير

تاريخ الدرجة العلمية

2004

الملخص العربي

بلغ حجم المعلومات وعدد الوثائق المحفوظة على شكل نصوص مكتوبة و بكافة لغات العالم حدا لا يمكن إحصاؤه, و لا يمكن التنبؤ بالحد الذي قد تصل إليه مستقبلا, و أصبحت عملية البحث عن معلومة معينة وسط هذا الكم الهائل تحتاج إلى وقت كبير.

من هنا فإن الضرورة تقتضي إيجاد وسائل بحث سريعة و غير تقليدية لتخدم هذا الغرض, حيث أن أسرع خوارزمية تقوم بهذا العمل هي خوارزمية بوير مور (Boyer Moore) و التي تعتمد على عدد قليل من المقارنات للأحرف, و القفزات الكبيرة التي تجريها على النص أثناء عملية البحث.

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

تعتمد المعالجة الأولية على عمل مصفوفة متغيرة الحجم تحتوي جميع مواقع حرف ما, و عمل مصفوفة ثابتة بطول (256) عنصرا و هو طول الأبجدية, المفترضة في هذه الدراسة على أنها مجموعة الشيفرة الأمريكية المعيارية لتبادل المعلومات (ASCII), و هذه المصفوفة مكونة من (256) مصفوفة متغيرة الحجم (أي مصفوفة لكل حرف في الأبجدية (ASCII)), و كل مصفوفة متغيرة الحجم لحرف ما تحتوي جميع مواقع ذلك الحرف في النص.

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

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

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

و تبين النتائج بان أداء هذه الخوارزميات المقترحة أفضل بكثير من أداء الخوارزميات التقليدية و بنسب تحسين كبيرة, و بأداء أفضل عند زيادة الأحمال.

التخصصات الرئيسية

تكنولوجيا المعلومات وعلم الحاسوب

الموضوعات

• البرمجة الخطية
• الفيزياء الرياضية
• الحواسيب
• برمجيات الحاسوب
• البرمجة الآلية

عدد الصفحات

76

قائمة المحتويات

• APA
• MLA
• AMA

لغة النص

العربية

نوع البيانات

رسائل جامعية

رقم السجل

BIM-307771