Performance study of the Memory Utilization of an Improved Pattern Matching Algorithm using Bit-Parallelism

John Abiodun Oladunjoye(1), Moses Timothy(2), Okpor James(3), Baku Agyo Raphael(4),


(1) Federal University Wukari, Wukari. Taraba State. Nigeria
(2) Federal University Lafia, Nasarawa State, Nigeria.
(3) Federal University Wukari, Wukari. Taraba State. Nigeria
(4) Federal University Wukari, Wukari. Taraba State. Nigeria

Abstract


The strategy of packing several data values in a single computer word and refreshing them all in a solitary operation is referred to bit parallelism. It assumes a significant part in pattern matching because it can handle in parallel the length of pattern sizes. In this paper, an Improved Pattern Matching model (IPM) proposed, which makes searching process quicker and decreases how much memory used in processing input data. C Sharp was used for the development of the model. With a computer word size of 64bits and pattern length ranging from 8 characters to 72 characters, the system decides how much memory is used. The developed model was evaluated and contrasted with the existing model using 64bits computer word size (cws) and the pattern length of 72 characters. The assessment showed that the IPM had minimal worth of MU contrasted with the existing model (BNDM, SBNDM, and FSBNDM). This IPM model can be embraced for improvement of the size of string data stored in computer word because of its capacity to diminish memory space usage.

Keywords


Bit-parallelism; pattern matching; string patter matching; memory utilization; improved pattern matching

Full Text:

PDF

References


Faro, S., and Lecroq, T. The Exact Online String Matching Problem: A Review of the most Recent Results”. ACM Computing Surveys, 2013; 45,2, 1-42.

Gulfishsan, F.A., and Nilay, K. String matching algorithms using bit parallelism. International Journal of Advanced Engineering and Global Technology, 2014; 2, 5, 667-671.

Alina, G. Bit parallel string matching. International Journal of Soft Computing and Engineering, 2006; 215-224.

Navarro, G., and Raffinot, M. Fast and flexible string matching by combining bit-parallelism and suffix automata. Journal of Exp. Algorithmics (JEA), 2000; 5, 4, 1-36.

Nimisha, S., and Deepak, G. String matching algorithms and their Applicability. Application International Journal of Soft Computing and Engineering (IJSCE), 2012; 1, 6, 2231-2307.

Kapil K.S, Rohit V, and Vivek S. Efficient string matching using bit-parallelism. International Journal of Computer Science and Information Technologies, 2015; 6, 1, 265-269.

Alberto Apostolico and ZviGalil. Pattern matching algorithms. Oxford University Press, USA, 1st edition, May 29, 1997.

Hudaib, A., Suleiman, D. and Awajan, A. Fast pattern matching algorithm using changing consecutive characters. Journal of Software Engineering and Applications, 2016; 9, 399-411.

Suleiman, D., Hudaib, A., Al-Anani, A., Al-Khalid, R. and Itriq, M. ERS-A Algorithm for Pattern Matching. Middle East Journal of Scientific Resarech, 2013; 15, 1067-1075.

Pendlimarri, D. and Petlu, P.B.B. Novel pattern matching algorithm for single pattern matching. International Journal on Computer Science and Engineering, 2010; 2, 2698-2704.

Hudaib, A., Al-Khalid, R Al-Anani, A., Itriq, M. and Suleiman, D. Four Sliding Windows Pattern Matching Algorithm (FSW). Journal of Software Engineering and Applications, 2015; 8, 154-165.

Faro, S. and Kulekci, M.O. Fast Packed String Matching for Short Patterns. 2012; ArXiv:1209.6449v1[cs.IR].

Berry, T., and Ravindran, K. A fast string matching algorithm and experimental results. Proceedings of the prague Stringology Club Workshop ‘99’Collaborative Report DC-99-05, Czech Technical University, Prague, 2001; 16-26.

Senapati, K.K., Mal, S. and Sahoo, G. RS-A Fast Pattern Matching Algorithm for Biological Sequences. International Journal of Engineering and Innovative Technology (IJEIT), 2012; 1, 116-118.

Suleiman, D. Enhanced Berry Ravindran Pattern Matching Algorithm (EBR). Life Science Journal, 2014; 11, 395-402.

Faro, S. Efficient variants of the Backward-Oracle-Matching Algorithm. International Journal of Foundations of Computer Science, 2009; 20, 967-984. http://dx.doi.org/10.1142/S0129054109006991

Salmela, L., Tarhio, J. and Kalsi, P. Approximate Boyer-Moore String Matching for Small Alphabets. Algorithmica, 2010; 58, 591-609. http://dx.doi.org/10.1007/s00453-009-9286-3

Suleiman, D., Hudaib, A., Al-Anani, A., Al-Khalid, R. and Itriq, M. ERS-A Algorithm for Pattern Matching. Middle East Journal of Scientific Resarech,2013; 15, 1067-1075.

Farro, S. and Lecroq, T, Twenty Years of Bit-parallelism in String Matching, 2000.

Rajesh, P. ,Suneeta, A., Ishadutta, Y. and Bharat, S. Efficient Bit-Parallel Multi-Patathens String Matching Algorithms for Limited Expression” ACM, 2010; J an. 22-23.

Peltola, H., and Tarhio, J. Alternative algorithms for bit-parallel string matching. In M.A Nascimento, E. Silvad e Moura, and A.L Oliveira, editors, proceedings of the 10th International Symposium on string processing and Information Retrieval SPIRE, 2003; 2857, 80-94. Manaus, Brazil, 2003. Springer-Verlag, Berlin.

Faro, S., and Lecroq, T. Efficient variations of the Backward-Oracle-Matching algorithm. In Holub Jan and Zdarek Jan, editors, Proceedings of the Prague stringology conference, 2008; 146-160, Czech Technical University in Prague, Czech Republic.

Sunday, D.M. A Fast Substring Search Algorithm. Communications of the ACM, 1990; 33, 8, 132-142.


Refbacks

  • There are currently no refbacks.


Journal of Computer Science and Engineering (JCSE)
ISSN 2721-0251 (online)
Published by : ICSE (Institute of Computer Sciences and Engineering)
Website : http://icsejournal.com/index.php/JCSE/
Email: jcse@icsejournal.com

Creative Commons License is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.