Fast hybrid string matching algorithm using message passing programming model
| dc.contributor.author | Abdul Rozaq, Atheer A. | |
| dc.date.accessioned | 2016-01-28T07:11:28Z | |
| dc.date.available | 2016-01-28T07:11:28Z | |
| dc.date.issued | 2009-06 | |
| dc.description.abstract | String matching is an operation that chec:ks the optimal alignment by comparisons between the characters in pattern and text. It has become highly important in the last two decades due to the advancement in technology. It has also become necessary to solve string matching problem because of its application in many fields. The consumed time, number of attempts and number of characters comparison are considered as problems during matching process. It is advisable to use an efficient and faster algorithm to complete the matching with higher speed and lowest cost. The aim ofthis study is to take advantage of Two way, Karp-Rabin andQuick search algorithms by formulating fast hybrid string matching algorithm that depends on the good properties at each of the algorithm mentioned above and to evaluate the hybrid algorithm in sequential and parallel phases. An experiment was conducted using C++ language and was applied on Aurora Cluster at the School of Computer Science in USM. Also, the methodology included the use of different types of standard databases with different pattern lengths and different number of processors during parallelization. The performance of the sequential algorithm is improved compared to the original algorithms. The hybrid algorithm showed less number of attempts, less number of characters comparison and consumed less time than original algorithms. The hybrid algorithm gives optimal results and performance during parallelization. It produced higher speedup, efficiency and percentage of performance gain when compared with the sequential. The performance in both parallel and sequential hybrid algorithm was influenced by the type of data. The Source code and English texts showed higher performance in sequential while DNA sequence showed a higher performance in parallel. | en_US |
| dc.identifier.uri | http://hdl.handle.net/123456789/1724 | |
| dc.language.iso | en | en_US |
| dc.subject | String matching algorithm | en_US |
| dc.subject | Passing programming model | en_US |
| dc.title | Fast hybrid string matching algorithm using message passing programming model | en_US |
| dc.type | Thesis | en_US |
Files
License bundle
1 - 1 of 1
Loading...
- Name:
- license.txt
- Size:
- 1.71 KB
- Format:
- Item-specific license agreed upon to submission
- Description: