An enhanced Boyer-Moore algorithm

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

تحسين خوارزمية بوير-مور

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

al-Mahasinah, Muadh Musa Hamdan

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

Ahmad, Mamun Khalid

أعضاء اللجنة

al-Sadi, Jihad A.
al-Hamid, Muhammad

الجامعة

جامعة الشرق الأوسط

الكلية

كلية تكنولوجيا المعلومات

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

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

دولة الجامعة

الأردن

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

ماجستير

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

2014

الملخص الإنجليزي

The volume of information and the number of computer documents has been increasing over the last years.

Thus, there is an urgent need for finding new fast efficient and non-traditional searching methods.

The fastest known traditional searching algorithm is the Boyer Moore algorithm, which depends on a small number of character comparisons, and large shifts that are performed on the text during search.

In this study, we propose a string matching algorithm which made an improvement on the pattern matching technique, the algorithm scans the text from both sides simultaneously using two windows; each window has a size that is equal to the pattern length.

Both windows move in parallel over the text until the first occurrence of the pattern is found or until both windows reach the middle of the text or intersection between both of the windows, all the process in this algorithm depend on the preprocessing phase in the Boyer Moore algorithm BM and Quick Search QS algorithm on the left window and the right window respectively over the text.

The experimental results show that the proposed algorithm BBQ algorithm has enhanced the process of pattern matching by reducing the number of comparisons performed.

The best time case is calculated where m is the length of the pattern and n is length of the text.

All previous enhancements aims to getting increase the selectivity of the algorithm and it affects the performance and effectiveness as reduces the time spent in the search process.

The BBQ algorithms and some traditional algorithms were implemented and compared.

The result shows that the performance of the BBQ algorithms is much better than of the traditional algorithms, including the Boyer-Moore algorithm.

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

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

عدد الصفحات

99

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

• APA
• MLA
• AMA

لغة النص

الإنجليزية

نوع البيانات

رسائل جامعية

رقم السجل

BIM-694046