Four Sliding Windows Pattern Matching Algorithm (FSW)

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

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

DOI: 10.4236/jsea.2015.83016                

Abstract

This paper presents an efficient pattern matching algorithm (FSW). FSW improves the searching process for a pattern in a text. It scans the text with the help of four sliding windows. The windows are equal to the length of the pattern, allowing multiple alignments in the searching process. The text is divided into two parts; each part is scanned from both sides simultaneously using two sliding windows. The four windows slide in parallel in both parts of the text. The comparisons done between the text and the pattern are done from both of the pattern sides in parallel. The conducted experiments show that FSW achieves the best overall results in the number of attempts and the number of character comparisons compared to the pattern matching algorithms: Two Sliding Windows (TSW), Enhanced Two Sliding Windows algorithm (ETSW) and Berry-Ravindran algorithm (BR). The best time case is calculated and found to be  while the average case time complexity is  .

Keywords

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

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Simone, F. and Thierry, L. (2013) The Exact Online String Matching Problem: A Review of the Most Recent Results. ACM Computing Surveys, 45, 13.
[2]	Yang, Z., Yu, J. and Kitsuregawa, M. (2010) Fast Algorithms for Top-k Approximate String Matching. Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, Atlanta, 11-15 July 2010.
[3]	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.
[4]	Bhukya, R. and Somayajulu, D. (2011) Article: Exact Multiple Pattern Matching Algorithm Using DNA Sequence and Pattern Pair. International Journal of Computer Applications, 17, 32-38. http://dx.doi.org/10.5120/2239-2862
[5]	Alsmadi, I. and Nuser, M. (2012) String Matching Evaluation Methods for DNA Comparison. International Journal of Advanced Science and Technology, 47, 13-32.
[6]	Bhandaru, J. and Kumar, A. (2014) A Survey of Fast Hybrid String Matching Algorithms. International Journal of Emerging Sciences, 4, 24-37.
[7]	Linhai, C. (2014) An Innovative Approach for Regular Expression Matching Based on NoC Architecture. International Journal of Smart Home, 8, 45-52. http://dx.doi.org/10.14257/ijsh.2014.8.1.06
[8]	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.
[9]	Singla, N. and Garg, D. (2012) String Matching Algorithms and Their Applicability in Various Appli-cations. International Journal of Soft Computing and Engineering (IJSCE), I, 218-222.
[10]	Guo, L., Du, S., Ren, M., Liu, Y., Li, J., He, J., Tian, N. and Li, K. (2013) Parallel Algorithm for Approximate String Matching with K Differences. IEEE Eighth International Conference on Net-working, Architecture and Storage, 17-19 July 2013, 257-261. http://dx.doi.org/10.1109/NAS.2013.40
[11]	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.
[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]	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, Collaborative Report DC-99-05, Czech Technical University, Prague, 16-26.
[15]	Khan, Z. and Pateriya, R.K. (2012) Multiple Pattern String Matching Methodologies: A Comparative Analysis. International Journal of Scientific and Research Publications, 2, 2250-3153.
[16]	Claude, F., Navarro, G., Peltola, H., Salmela, L. and Tarhio, J. (2012) String Matching with Alphabet Sampling. Journal of Discrete Algorithms, 11, 37-50. http://dx.doi.org/10.1016/j.jda.2010.09.004
[17]	Zhang, P. and Liu, J. (2011) An Improved Pattern Matching Algorithm in the Intrusion Detection System. Applied Mechanics and Materials, 48-49, 203-207. http://dx.doi.org/10.4028/www.scientific.net/AMM.48-49.203
[18]	Faro, S. and Lecroq, T. (2012) A Multiple Sliding Windows Approach to Speed Up String Matching Algorithms. SEA, 172-183.
[19]	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.