Research Article Open Access

A Fast Hybrid Algorithm for the Exact String Matching Problem

Abdulwahab Ali Al-mazroi1 and Nur’Aini Abdul Rashid1
  • 1 , Afganistan
American Journal of Engineering and Applied Sciences
Volume 4 No. 1, 2011, 102-107

DOI: https://doi.org/10.3844/ajeassp.2011.102.107

Submitted On: 8 September 2010 Published On: 31 January 2011

How to Cite: Al-mazroi, A. A. & Rashid, N. A. (2011). A Fast Hybrid Algorithm for the Exact String Matching Problem. American Journal of Engineering and Applied Sciences, 4(1), 102-107. https://doi.org/10.3844/ajeassp.2011.102.107

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.

  • 1,489 Views
  • 2,310 Downloads
  • 6 Citations

Download

Keywords

  • Hybrid algorithm
  • string matching
  • pre-processing phase
  • searching phase