A Fast Hybrid Algorithm for the Exact String Matching Problem
- 1 University Science Malaysia, Malaysia
Abstract
Problem statement: Due to huge amount and complicated nature of data being generated recently, the usage of one algorithm for string searching was not sufficient to ensure faster search and matching of patterns. So there is the urgent need to integrate two or more algorithms to form a hybrid algorithm (called BRSS) to ensure speedy results. Approach: This study proposes the combination of two algorithms namely Berry-Ravindran and Skip Search Algorithms to form a hybrid algorithm in order to boost search performance. Results: The proposed hybrid algorithm contributes to better results by reducing the number of attempts, number of character comparisons and searching time. The performance of the hybrid was tested using different types of data-DNA, Protein and English text. The percentage of the improvements of the hybrid algorithm compared to Berry-Ravindran in DNA, Protein and English text are 50%, 43% and 44% respectively. The percentage of the improvements over Skip Search algorithm in DNA, Protein and English text are 20%, 30% and 18% respectively. The criteria applied for evaluation are number of attempts, number of character comparisons and searching time. Conclusion: The study shows how the integration of two algorithms gives better results than the original algorithms even the same data size and pattern lengths are applied as test evaluation on each of the algorithms.
DOI: https://doi.org/10.3844/ajeassp.2011.102.107
Copyright: © 2011 Abdulwahab Ali Al-mazroi and Nur’Aini Abdul Rashid. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
- 4,634 Views
- 3,538 Downloads
- 9 Citations
Download
Keywords
- Hybrid algorithm
- string matching
- pre-processing phase
- searching phase