An enhanced Boyer-Moore algorithm
Other Title(s)
تحسين خوارزمية بوير-مور
Dissertant
al-Mahasinah, Muadh Musa Hamdan
Thesis advisor
Comitee Members
al-Sadi, Jihad A.
al-Hamid, Muhammad
University
Middle East University
Faculty
Faculty of Information Technology
Department
Computer Science Department
University Country
Jordan
Degree
Master
Degree Date
2014
English Abstract
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.
Main Subjects
Information Technology and Computer Science
No. of Pages
99
Table of Contents
Table of contents.
Abstract.
Abstract in Arabic.
Chapter One : Introduction.
Chapter Two : String searching algorithms.
Chapter Three : Literature survey.
Chapter Four : The proposed algorithm bidirectional Boyer Moore and quick search (BBQ).
Chapter Five : Experimental results.
Chapter Six : Conclusion and future work.
References.
American Psychological Association (APA)
al-Mahasinah, Muadh Musa Hamdan. (2014). An enhanced Boyer-Moore algorithm. (Master's theses Theses and Dissertations Master). Middle East University, Jordan
https://search.emarefa.net/detail/BIM-694046
Modern Language Association (MLA)
al-Mahasinah, Muadh Musa Hamdan. An enhanced Boyer-Moore algorithm. (Master's theses Theses and Dissertations Master). Middle East University. (2014).
https://search.emarefa.net/detail/BIM-694046
American Medical Association (AMA)
al-Mahasinah, Muadh Musa Hamdan. (2014). An enhanced Boyer-Moore algorithm. (Master's theses Theses and Dissertations Master). Middle East University, Jordan
https://search.emarefa.net/detail/BIM-694046
Language
English
Data Type
Arab Theses
Record ID
BIM-694046
