New Searching Technique of Hybrid Exact String Matching Algorithm

Atheer Akram Abdulrazzaq; Nur’Aini Abdul Rashid; Muhannad A. Abu-Hashem; Zurinahni Zainol

doi:10.15866/irecos.v11i10.10321

New Searching Technique of Hybrid Exact String Matching Algorithm

Atheer Akram Abdulrazzaq^(1*), Nur’Aini Abdul Rashid⁽²⁾, Muhannad A. Abu-Hashem⁽³⁾, Zurinahni Zainol⁽⁴⁾

^(*) Corresponding author

Authors' affiliations

DOI: https://doi.org/10.15866/irecos.v11i10.10321

Abstract

String matching algorithms play a significant role in solving the fundamental problems of computer sciences. This study proposed a new hybrid string matching algorithm called AbdulRazzaq. This algorithm consisted of a combination between the new searching technique and selecting the good features from two original algorithms, namely, Smith and Karp–Rabin. The proposed algorithm showed lower number of attempts and character comparisons than those of the original algorithms and common algorithms in the string matching field. AbdulRazzaq algorithm used six types of databases, namely, DNA, Protein, XML, Pitch, English, and Source. The best database regarding the number of attempts of AbdulRazzaq algorithm was Pitch, whereas DNA was the worst. This algorithm can work with good performance in the number of character comparisons with all databases.
Copyright © 2016 Praise Worthy Prize - All rights reserved.

Keywords

String Matching Algorithms; AbdulRazzaq Algorithm; Type of Database

Full Text:

PDF

References

Abdulrazzaq, A.A., Abdul Rashid, N., Hamdani, H.B.Y., Ghadban, R.M., Mahmood, A.W., Influenced Factors on Computation Among Quick Search, Two-Way and Karp-Rabin Algorithms, Proceeding of the 3rd International Conference on Informatics and Technology (Informatics '09)(Page: 100 Year of Publication:2009).
http://dx.doi.org/10.1109/icctd.2009.198

D. Xu, H. Zhang, Y. Fan,The GPU-based High-performance Pattern-matching Algorithm for Intrusion Detection, (2013) Journal of Computational Information System(JCIS), 9 (10), pp.3791-3800.
http://dx.doi.org/10.1109/mines.2009.175

R. Bhukya, D. Somayajulu, Index Based Multiple Pattern Matching Algorithm Using DNA Sequence and Pattern Count, (2011) International Journal of Information Technology and Knowledge Management(IJCA) , 4(2), pp. 431- 441.
http://dx.doi.org/10.5120/2239-2862

C.W. Lu, String Matching Algorithms Based upon the Uniqueness Property and an Approximate String Matching Algorithm, M.Sc. Thesis, Dept, Computer Science and Information Engineering National Chi-Nan University, Nantou County, Taiwan, 2008.
http://dx.doi.org/10.1007/978-3-540-39984-1_8

C. Charras, T. Lecroq, Handbook of Exact String-Matching Algorithms (King's College Publications, 2004).
http://dx.doi.org/10.1007/978-0-387-30162-4_365

Radhakrishna, V., Phaneendra, B., Kumar, V.S., A Two Way Pattern Matching Algorithm Using Sliding Patterns, 3rd International Conference on Advanced Computer Theory and Engineering (ICACTE) (Page: 666 Year of Publication: 2010 ISBN : 9781424465392).
http://dx.doi.org/10.1109/icacte.2010.5579739

I. Hussain, S.Z.H. Kazmi, I.A Khan, R. Mehmood, Improved-Bidirectional Exact Pattern Matching, (2013) International Journal of Scientific & Engineering Research (IJCSI), 4(5), pp.659-663.
http://dx.doi.org/10.1080/10286020.2011.619183

Ersin, A.K., Carus, A., Mesut, A., The Efficiency of String Matching Algorithms on Natural Languages Text, International Scientific Conference, untech07 (Gabrovo) (Page : 349 Year of Publication: 2007 ISBN: 954-683-167-0.
http://dx.doi.org/10.1109/eit.2007.4374455

H.M. Chen, An Exact String Matching Problem Using Data Encoding Scheme, M.Sc. Thesis, Dept, Computer Science and Information Engineering National Chi-Nan University, Nantou County, Taiwan, 2008.
http://dx.doi.org/10.5614/j.eng.technol.sci.2014.46.4.1

R.N. Horspool, Practical fast searching in strings, (1980) Journal of Software-practice and experience, 10(6), pp. 501-506.
http://dx.doi.org/10.1002/spe.4380100608

D.M. Sunday, A very fast substring search algorithm, (1990) Journal of Communications of the Association for Computing Machinery, 33(8), pp.132–142.
http://dx.doi.org/10.1145/79173.79184

A.F. Klaib, Z. Zainol, N.H. Ahamed, R. Ahmad, W. Hussin, Application of Exact String Matching Algorithms towards SMILES Representation of Chemical Structure, (2007) International Journal of Computer and Information Science and Engineering(WASET ), 1(10), pp.235-239.
http://dx.doi.org/10.1016/j.ipl.2007.01.002

Y. Chen-Cheng, A Combination of Berry Ravindran Algorithm and Two Way Algorithm for Exact String Matching, M.Sc. Thesis, Dept, Computer Science and Information Engineering National Chi-Nan University, Nantou County, Taiwan, 2008.
http://dx.doi.org/10.3844/jcssp.2011.644.650

Cantone ,D., Faro, S., Fast-search: A new efficient variant of the Boyer–Moore string matching algorithm, Proceedings of the 2nd international conference on Experimental and efficient algorithms, Springer-Verlag (Page: 47 Year of Publication: 2003 ISBN: 3-540-40205-5).
http://dx.doi.org/10.1007/3-540-44867-5_4

Kalsi, P., Peltola, H., Tarhio, J., Comparison of exact string matching algorithms for biological sequences, In Proc. BIRD 2008, 2nd International Conference on Bioinformatics Research and Development, Communications in Computer and Information Science, Springer (Page: 417 Year of Publication: 2008 ISBN: 978-3-540-70598-7) .
http://dx.doi.org/10.1007/978-3-540-70600-7_31

S.S. Sheik, S.K. Aggarwal, A. Poddar, N. Balakrishnan, K. Sekar, A fast pattern matching algorithm, (2004) Journal of Chemical Information and Computer Sciences, 44, pp. 1251–1256.
http://dx.doi.org/10.1021/ci030463z

R. Thathoo, A. Virmani, S.S. Lakshmi, N. Balakrishnan, K. Sekar, TVSBS: A fast exact pattern matching algorithm for biological sequences, (2006) Current Science Journal, 9(1), pp.47–53.
http://dx.doi.org/10.1109/bmei.2008.154

A.A. AbdulRazzaq, N. Abdul Rashid, A.N.B. Ali, Fast Hybrid String Matching Algorithm, (2013) International Journal of Digital Content Technology and its Applications (JDCTA), 7(10), pp.62-71.
http://dx.doi.org/10.4156/jdcta.vol7.issue10.7

H.A. Kadhim, New Sequential and Gpu-Based Hybrid String Matching Algorithms, M.Sc. Thesis, Dept, Computer Science School, University Science Malaysia (USM), Penang, Malaysia 2012.
http://dx.doi.org/10.17113/ftb.53.03.15.3907

W. Stein, Elementary Number Theory: Primes, Congruences, and Secrets ( First edition, Springer, 2, 2011).
http://dx.doi.org/10.1007/b13279

Pizzachili. Pizza ChiliCorpus. (14Jan 2009) [online]. From URL: http://pizzachili.dcc.uchile.cl/,2009.
http://dx.doi.org/10.5860/choice.46-6346

Huang, Y., Ping, L., Pan, X., Cai, G., A Fast Exact Pattern Matching Algorithm for Biological Sequences, International Conference on Biomedical Engineering and Informatics (BMEI) (Page: 8 Year of publication: 2008 ISBN: 978-0-7695-3118-2).
http://dx.doi.org/10.1109/bmei.2008.154

Cai, G., Nie, X., Huang, Y., A Fast Hybrid Pattern Matching Algorithm for Biological Sequences, Proceedings of 2nd nternational Conference on Biomedical Engineering and Informatics (BMEI '09) ( Page: 1 Year of Publication: 2009 ).
http://dx.doi.org/10.1109/bmei.2009.5305645

P. Ferragina, R. Gonz´alez, G. Navarro, R. Venturini, Compressed text indexes: From theory to practice, (2009) Journal of Experimental Algorithmics (JEA), 13(12), pp.1-27.
http://dx.doi.org/10.1145/1412228.1455268

R. Venturin, On searching and extracting strings from compressed textual data, Ph.D thesis, Dept, Computer Science, Pisa University,Pisa, Italy, 2010.
http://dx.doi.org/10.15420/ecr.2016.11.1

Karkkainen, J., Joong, C.N., Faster Filters for Approximate String Matching. Proceedings of the Nine Workshop on Algorithm Engineering and Experiments, ALENEX (Page: 84 Year of publication: 2007 ISBN: 978-1-61197-287-0.
http://dx.doi.org/10.1137/1.9781611972870.8

Klaib, A.F., Osborne, H., BRQS Matching Algorithm for Searching Protein Sequence Databases, ICFCC '09 Proceedings of the 2009 International Conference on Future Computer and Communication, IEEE Computer Society Washington ( Page: 223 Year of Publication: 2009 ISBN: 978-0-7695-3591-3).
http://dx.doi.org/10.1109/icfcc.2009.40

V. Kurt, Protein Structure Prediction using Decision Lists, M.Sc. Thesis, Dept, Computational Sciences and Engineering, Koç University, İstanbul, Turkey, 2005.
http://dx.doi.org/10.18535/ijsshi/v2i10.04

Chew, E., Chen, Y.C., Mapping Midi to the Spiral Array: Disambiguating Pitch Spellings, Computational Modeling and Problem Solving in the Networked World, Proceedings of the 8th INFORMS Computer Society Conference, ICS2003 (Page: 259 Year of Publication: 2003).
http://dx.doi.org/10.1007/978-1-4615-1043-7_13

Ferragina P, Fischer J. Suffix Arrays on Words. Lecture Notes in Computer Science, Springer-Verlag (Page: 328 Year of Publication: 2007).
http://dx.doi.org/10.1007/978-3-540-73437-6_33

R.A. Deighton, Using Rabin-Karp fingerprints and LevelDB for faster searches, M.Sc. Thesis, Dept, Department of Computer Science, University of Ontario Institute of Technology (UOIT), Oshawa, Canada, 2012.
http://dx.doi.org/10.4095/123142

R. Nidadavolu, Content-based Retrieval of Music Using Monophonic Queries on a Database of Polyphonic, (MIDI Information. ProQuest information and learning company, 2008).
http://dx.doi.org/10.1007/978-3-642-23141-4_25

Crochemore, M., Lecroq, T., A fast implementation of the Boyer–Moore string matching algorithm, LITIS (Page: 1 Year of publication: 2008).
http://dx.doi.org/10.1007/978-0-387-30162-4_365

Refbacks

There are currently no refbacks.

Username
Password
Remember me