BM-KMP hybrid algorithm for exact and subsequence string matching
| dc.contributor.author | W. Mahmood, Ammar | |
| dc.date.accessioned | 2015-07-30T05:31:12Z | |
| dc.date.available | 2015-07-30T05:31:12Z | |
| dc.date.issued | 2009 | |
| dc.description.abstract | String matching algorithm is a basic operation in computer science. Some of the example applications of this operation are text searching, sequence alignment in computational biology and internet search engine. The size of the databases of these applications are growing very rapidly, having different types of data, therefore more efficient string matching algorithm is required to solve this problem. This study focuses in hybridizing two well-known exact string matching algorithms which are Boyer- Moore and Knuth-Morris-Pratt string matching algorithms. The hybrid algorithm employs main ideas of the two phases of Boyer-Moore and Knuth-Morris~Pratt algorithms. The hybrid algorithm employs good prefix idea from Knuth-Morris-Pratt algorithm and bad character shifting from Boyer-Moore algorithm. Then the proposed hybrid algorithm was adapted for subsequence matching with some modifications in preprocessing phase and search phase. Both the hybrid and enhanced algorithms were tested using four types of alphabet which are binary alphabets, DNA alphabet, protein alphabet and English alphabet. The results of these algorithms show better results compared to Boyer-Moore and Knuth-Morris-Pratt algorithms in terms of time and the number of characters compared in different sizes of alphabet. The two algorithms also showed better results than Knuth-Morris-Pratt algorithm in all types of alphabet, and better result than Boyer-Moore algorithm ·_in binary, DNA' ·and protein alphabet. However, the algorithms perfonned worse than Boyer-Moore algorithm in English alphabet. | en_US |
| dc.identifier.uri | http://hdl.handle.net/123456789/1054 | |
| dc.language.iso | en | en_US |
| dc.subject | Algorithm | en_US |
| dc.subject | String matching | en_US |
| dc.title | BM-KMP hybrid algorithm for exact and subsequence string matching | 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: