Enhancing ERS-A Algorithm for Pattern Matching (EERS-A)

Dima Suleiman¹, Mariam Itriq¹, Aseel Al-Anani², Rola Al-Khalid², Amjad Hudaib²

¹Department of Business Information Technology, King Abdullah II School for Information Technology, The University of Jordan, Amman, Jordan.
²Department of Computer Information Systems, King Abdullah II School for Information Technology, The University of Jordan, Amman, Jordan.

DOI: 10.4236/jsea.2015.83015                

Abstract

Pattern matching is a very important topic in computer science. It has been used in various applications such as information retrieval, virus scanning, DNA sequence analysis, data mining, machine learning, network security and pattern recognition. This paper has presented a new pattern matching algorithm—Enhanced ERS-A, which is an improvement over ERS-S algorithm. In ERS-A, two sliding windows are used to scan the text from the left and the right simultaneously. The proposed algorithm also scans the text from the left and the right simultaneously as well as making comparisons with the pattern from both sides simultaneously. The comparisons done between the text and the pattern are done from both sides in parallel. The shift technique used in the Enhanced ERS-A is the four consecutive characters in the text immediately following the pattern window. The experimental results show that the Enhanced ERS-A has enhanced the process of pattern matching by reducing the number of comparisons performed.

Keywords

Pattern Matching, Enhanced Two Sliding Windows Algorithm, RS-A Fast Pattern Matching Algorithm, Enhanced RS-A

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	El Emary, I.M.M. and Jaber, M.S.M. (2008) A New Approach for Solving String Matching Problem through Splitting the Unchangeable Text. World Applied Sciences Journal, 4, 626-633.
[2]	Chao, Y. (2012) An Improved BM Pattern Matching Algorithm in Intrusion Detection System. Applied Mechanics and Materials, 148-149, 1145-1148.
[3]	Diwate, R. and Alaspurkar, S. (2013) Study of Different Algorithms for Pattern Matching. International Journal of Advanced Research in Computer Science and Software Engineering, 3, 615-620.
[4]	Bhukya, R. and Somayajulu, D. (2010) An Index Based Forward Backward Multiple Pattern Matching Algorithm. World Academy of Science, Engineering and Technology, 4, 1513-1521.
[5]	Senapati, K.K., Mal, S. and Sahoo, G. (2012) RS-A Fast Pattern Matching Algorithm for Bio-Logical Sequences. International Journal of Engineering and Innovative Technology (IJEIT), 1, 116-118.
[6]	Bhukya, R. and Somayajulu, D. (2011) Multiple Pattern Matching Algorithm Using Pair-Count. IJCSI International Journal of Computer Science Issues, 8, 1694-0814.
[7]	Faro, S. (2009) Efficient Variants of the Backward-Oracle-Matching Algorithm. International Journal of Foundations of Computer Science, 20, 967-984. http://dx.doi.org/10.1142/S0129054109006991
[8]	Faro, S. and Külekci, M.O. (2012) Fast Packed String Matching for Short Patterns. arXiv:1209.6449v1 [cs.IR]
[9]	Salmela, L., Tarhio, J. and Kalsi, P. (2010) Approximate Boyer-Moore String Matching for Small Alphabets. Algorithmica, 58, 591-609.
[10]	Itriq, M., Hudaib, A., Al-Anani, A., Al-Khalid, R. and Suleiman, D. (2012) Enhanced Two Sliding Windows Algorithm for Pattern Matching (ETSW). Journal of American Science, 8, 607-616.
[11]	Suleiman, D., Hudaib, A., Al-Anani, A., Al-Khalid, R. and Itriq, M. (2013) ERS-A Algorithm for Pattern Matching. Middle East Journal of Scientific Research, 15, 1067-1075.
[12]	Hudaib, A., Al-Khalid, R., Suleiman, D., Itriq, M. and Al-Anani, A. (2008) A Fast Pattern Matching Algorithm with Two Sliding Windows (TSW). Journal of Computer Science, 4, 393-401. http://dx.doi.org/10.3844/jcssp.2008.393.401
[13]	Suleiman, D. (2014) Enhanced Berry Ravindran Pattern Matching Algorithm (EBR). Life Science Journal, 11, 395-402.
[14]	Al-Mazroi, A. and Rashid, N. (2011) A Fast Hybrid Algorithm for the Exact String Matching Problem. American Journal of Engineering and Applied Sciences, 4, 102-107.
[15]	Berry, T. and Ravindran, S. (2001) A Fast String Matching Algorithm and Experimental Results. In: Holub, J. and Simanek, M., Eds., Proceedings of the Prague Stringology Club Workshop’99, Colla-borative Report DC-99-05, Czech Technical University, Prague, 16-26.
[16]	Boyer, R.S. and Moore, J.S. (1977) A Fast String Searching Algorithm. Communications of the Association for Computing Machinery, 20, 762-772. http://dx.doi.org/10.1145/359842.359859
[17]	Pendlimarri, D. and Petlu, P.B.B. (2010) Novel Pattern Matching Algorithm for Single Pattern Matching. International Journal on Computer Science and Engineering, 2, 2698-2704.
[18]	Hussain, I., Kausar, S., Hussain, L. and Khan, M. (2013) Improved Approach for Exact Pattern Matching (Bidirectional Exact Pattern Matching). International Journal of Computer Science Issues, 10, 59-65.
[19]	Bhandaru, J. and Kumar, A. (2014) A Survey of Fast Hybrid String Matching Algorithms. International Journal of Emerging Sciences, 4, 24-37.
[20]	Hussain, I., Kazmi, S., Khan, I. and Mehmood, R. (2013) Improved-Bidirectional Exact Pattern Matching. International Journal of Scientific & Engineering Research, 4, 659-663.
[21]	Hlayel Abdallah, A. and Hnaif Adnan, A. (2014) A New Exact Pattern Matching Algorithm (WEMA). Journal of Applied Sciences, 14, 193-196.
[22]	Calgary Corpus. ftp://ftp.cpsc.ucalgary.ca/pub/projects/text.compression.corpus/