A Fast Hybrid Algorithm for the Exact String Matching Problem | Science Publications

American Journal of Engineering and Applied Sciences

Abdulwahab A. Al-mazroi¹  Nur'Aini A. Rashid¹ 

关键词: Hybrid algorithm;    string matching;    pre-processing phase;    searching phase;   

DOI  :  10.3844/ajeassp.2011.102.107

学科分类：工程和技术（综合）

来源: Science Publications

【 摘 要 】

Problem statement: Due to huge amount and complicated nature of data being generatedrecently, the usage of one algorithm for string searching was not sufficient to ensure faster search andmatching of patterns. So there is the urgent need to integrate two or more algorithms to form a hybridalgorithm (called BRSS) to ensure speedy results. Approach: This study proposes the combination oftwo algorithms namely Berry-Ravindran and Skip Search Algorithms to form a hybrid algorithm inorder to boost search performance. Results: The proposed hybrid algorithm contributes to betterresults by reducing the number of attempts, number of character comparisons and searching time. Theperformance of the hybrid was tested using different types of data-DNA, Protein and English text. Thepercentage 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 improvementsover Skip Search algorithm in DNA, Protein and English text are 20%, 30% and 18% respectively. Thecriteria applied for evaluation are number of attempts, number of character comparisons and searchingtime. Conclusion: The study shows how the integration of two algorithms gives better results than theoriginal algorithms even the same data size and pattern lengths are applied as test evaluation on each ofthe algorithms.

【 授权许可】

Unknown