خوارزميات بحث سريعة للسلاسل الحرفية
Other Title(s)
Fast string searching algorithms
Dissertant
Thesis advisor
Comitee Members
العكور، محمد علي أحمد
الربابعة، مأمون
العبادي، محمد علي
University
Al albayt University
Faculty
Prince Hussein Bin Abdullah Faculty for Information Technology
Department
Department of Computer Science
University Country
Jordan
Degree
Master
Degree Date
2004
Arabic Abstract
بلغ حجم المعلومات وعدد الوثائق المحفوظة على شكل نصوص مكتوبة و بكافة لغات العالم حدا لا يمكن إحصاؤه, و لا يمكن التنبؤ بالحد الذي قد تصل إليه مستقبلا, و أصبحت عملية البحث عن معلومة معينة وسط هذا الكم الهائل تحتاج إلى وقت كبير.
من هنا فإن الضرورة تقتضي إيجاد وسائل بحث سريعة و غير تقليدية لتخدم هذا الغرض, حيث أن أسرع خوارزمية تقوم بهذا العمل هي خوارزمية بوير مور (Boyer Moore) و التي تعتمد على عدد قليل من المقارنات للأحرف, و القفزات الكبيرة التي تجريها على النص أثناء عملية البحث.
تقترح هذه الدراسة عدة خوارزميات للبحث في النصوص عن السلاسل الحرفية بشكل سريع و فعال, حيث تعتمد على معالجة أولية تجريها على النص و ليس على النماذج المبحوثة كما تفعل الخوارزميات التقليدية.
تعتمد المعالجة الأولية على عمل مصفوفة متغيرة الحجم تحتوي جميع مواقع حرف ما, و عمل مصفوفة ثابتة بطول (256) عنصرا و هو طول الأبجدية, المفترضة في هذه الدراسة على أنها مجموعة الشيفرة الأمريكية المعيارية لتبادل المعلومات (ASCII), و هذه المصفوفة مكونة من (256) مصفوفة متغيرة الحجم (أي مصفوفة لكل حرف في الأبجدية (ASCII)), و كل مصفوفة متغيرة الحجم لحرف ما تحتوي جميع مواقع ذلك الحرف في النص.
عندما يراد البحث عن سلسلة حرفية ما فان هذه الخوارزميات سوف تستخدم إحدى هذه المصفوفات في عملية البحث بدلا من عملية مسح النص كاملا, حيث أن طول المصفوفة المستخدمة في المعدل حتما سيكون اقل من حجم النص, و هذا بالتأكيد سيقلل من الوقت اللازم لإنهاء عملية البحث.
بالإضافة إلى المعالجة الأولية, تم اعتماد بعض التحسينات الإضافية على هذه الخوارزميات, مثل مقارنة الحرف الأخير قبل عملية المقارنة الكلية للأحرف, و استخدام مصفوفة الحرف الأقل تكرارا الذي يقلل من الوقت بشكل كبير, و كذلك مقارنة الحرف الأول و الأخير قبل إجراء عملية المقارنة مما يزيد من الانتقائية للخوارزمية, و ينعكس ذلك على أداءها و فعاليتها حيث يقلل من الوقت المستهلك في عملية البحث.
تمت في هذه الدراسة برمجة جميع الخوارزميات المقترحة و كذلك برمجة عدة خوارزميات تقليدية و مقارنة نتائجها.
و تبين النتائج بان أداء هذه الخوارزميات المقترحة أفضل بكثير من أداء الخوارزميات التقليدية و بنسب تحسين كبيرة, و بأداء أفضل عند زيادة الأحمال.
Main Subjects
Information Technology and Computer Science
Topics
No. of Pages
76
Table of Contents
فهرس المحتويات / الموضوعات.
الملخص / المستخلص.
الفصل الأول : مقدمة الدراسة.
الفصل الثاني : خوارزميات بحث السلاسل الحرفية.
الفصل الثالث : الخوارزميات المقترحة.
الفصل الرابع : النتائج و المقارنة.
قائمة المراجع.
American Psychological Association (APA)
الحسنات، أحمد بشير عبد الله. (2004). خوارزميات بحث سريعة للسلاسل الحرفية. (أطروحة ماجستير). جامعة آل البيت, الأردن
https://search.emarefa.net/detail/BIM-307771
Modern Language Association (MLA)
الحسنات، أحمد بشير عبد الله. خوارزميات بحث سريعة للسلاسل الحرفية. (أطروحة ماجستير). جامعة آل البيت. (2004).
https://search.emarefa.net/detail/BIM-307771
American Medical Association (AMA)
الحسنات، أحمد بشير عبد الله. (2004). خوارزميات بحث سريعة للسلاسل الحرفية. (أطروحة ماجستير). جامعة آل البيت, الأردن
https://search.emarefa.net/detail/BIM-307771
Language
Arabic
Data Type
Arab Theses
Record ID
BIM-307771
