CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Bit Parallel String Matching Algorithms: A Survey

by Sumit Gupta, Akhtar Rasool
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 95 - Number 10
Year of Publication: 2014
Authors: Sumit Gupta, Akhtar Rasool
10.5120/16632-6501

Sumit Gupta, Akhtar Rasool . Bit Parallel String Matching Algorithms: A Survey. International Journal of Computer Applications. 95, 10 ( June 2014), 27-32. DOI=10.5120/16632-6501

@article{ 10.5120/16632-6501,
author = { Sumit Gupta, Akhtar Rasool },
title = { Bit Parallel String Matching Algorithms: A Survey },
journal = { International Journal of Computer Applications },
issue_date = { June 2014 },
volume = { 95 },
number = { 10 },
month = { June },
year = { 2014 },
issn = { 0975-8887 },
pages = { 27-32 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume95/number10/16632-6501/ },
doi = { 10.5120/16632-6501 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:19:06.868417+05:30
%A Sumit Gupta
%A Akhtar Rasool
%T Bit Parallel String Matching Algorithms: A Survey
%J International Journal of Computer Applications
%@ 0975-8887
%V 95
%N 10
%P 27-32
%D 2014
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The intrinsic parallelism in bit operations like AND/OR inside a computer word is known as bit parallelism. Since 1992, this bit parallelism is directly used in string matching for matching efficiency improvement. Some of the popular bit parallel string matching algorithms Shift OR, Shift OR with Q-Gram, BNDM, TNDM, SBNDM, LBNDM, FBNDM, BNDMq, and Multiple pattern BNDM. This paper discusses the working of various bit parallel string matching algorithms with example. Here we present how bit parallelism is useful for efficiency improvement in various algorithms.

References
  1. Vidya Saikrishna, Akhtar Rasool and Nilay Khare, "Time Efficient String Matching Solution for Single and Multiple Pattern using Bit Parallelism", In procd. Of International Journal of Computer Applications (0975 – 8887) Volume 46– No. 6, May 2012.
  2. Christian Charras and Thierry Lecroq," Handbook of Exact String_Matching Algorithms", Published in King's college publication, Feb 2004.
  3. Ali Peiravi, "Application of string matching in Internet Security and Reliability", Marsland Press Journal of American Science, 6(1), pp. 25-33, 2010.
  4. Pei-fei Wu and Hai-juanShen,"The Research and Amelioration of Pattern-matching Algorithm in Intrusion Detection System", In the proc. of IEEE 14th International Conference on High Performance Computing and Communication & IEEE 9th International Conference on Embedded Software and Systems (HPCC-ICESS), pp. 1712-1715, 25-27 June 2012.
  5. Ramazan S. Aygün "structural-to-syntactic matching similar documents", Journal Knowledge and Information Systems, ACM Digital Library, Volume 16 Issue 3, pages 303-329, Aug 2008.
  6. Sanchez D. , Martin-Bautista M. J. , Blanco I. and Torre C. ," Text Knowledge Mining: An Alternative to Text Data Mining", In the proc. of IEEE International Conference on Data Mining Workshops, ICDMW '08, pp. 664-672, 15-19Dec. 2008.
  7. Robert M. Horton,Ph. D. "Bioinformatics Algorithm Demonstrations in Microsoft Excel", California State University, Sacramento, 2004.
  8. Knuth D E, Morris Jr J. H and Pratt V. R," Fast pattern matching in strings", In the procd. Of SIAM J. Comput. , Vol. 6, 1, pp. 323–350, 1977.
  9. Boyer R S and Moore J S,"A fast string searching algorithm", Communication of ACM 20, Vol. 10, pp. 762–772, 1977.
  10. Zhengda Xiong,"A Composite Boyer-Moore Algorithm for the String Matching Problem", In the proc. of International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT), pp. 492-496, 8-11 Dec 2010.
  11. Horspool R N,"Practical fast searching in strings", In proc. Of Software Practical Exp, Vol. 10, 6, pp. 501–506, 1980.
  12. Timo Raita,"Tuning the Boyer–Moore–Horspool String Searching Algorithm", In the proc. of Software Practice and Experience, Vol. 22(10), pp. 879–884, Oct. 1992.
  13. JingboYuan, Jinsong Yang and Shunli Ding," An Improved Pattern Matching Algorithm Based on BMHS", In the proc. Of 11th International Symposium on Distributed Computing and Applications to Business, Engineering & Science, 2012.
  14. Yuting Han and Guoai Xu, "Improved Algorithm of Pattern Matching based on BMHS", In the proc. of IEEE International Conference on Information Theory and Information Security (ICITIS), pp. 238-241, 17-19 Dec 2010.
  15. Jingbo Yuan, Jisen Zheng and Shunli Ding, "An Improved Pattern Matching Algorithm", In the proc. of Third International Symposium on Intelligent Information Technology and Security Informatics (IITSI), pp. 599-603, 2-4 April 2010.
  16. Linquan Xie, Xiaoming Liu and Guangxue Yue, "Improved Pattern Matching Algorithm of BMHS", In the proc. of International Symposium on Information Science and Engineering (ISISE), pp. 616-619, 24-26 Dec 2010.
  17. Commentz-Walter, "A string matching algorithm fast on the average," In the Proc. of 6th International Colloquium on Automata, Languages, and Programming, pp. 118–132,1979.
  18. Kouzinopoulos, C. S. and Margaritis, K. G. ,"A Performance Evaluation of the Pre-processing Phase of Multiple Keyword Matching Algorithms", In the proc. of 15th Panhellenic Conference on Informatics (PCI), pp. 85-89, 30 Sept 2011- 2 Oct 2011.
  19. Yang Dong hong, XuKe and Cui Yong,"An improved Wu-Manber multiple patterns matching algorithm", In the proc. Of 25th IEEE International Performance, Computing, and Communications Conference, IPCCC, pp. 680, 10-12 April 2006.
  20. Baojun Zhang , XiaoPing Chen , Lingdi Ping , Wu, Zhaohui, "Address Filtering Based Wu-Manber Multiple Patterns Matching Algorithm", In the proc. of 2009 Second International Workshop on Computer Science and Engineering[WCSE], Qingdao, Vol. 1, pp. 408 – 412,28-30 Oct. 2009.
  21. Alfred v aho and Margaret j corasick,"efficient string matching: an aid to bibliographic search" communication of acm, vol. 18, June 1975.
  22. Tao Tao and Mukherjee A. ,"Multiple-pattern matching in LZW compressed files using Aho-Corasick algorithm", In the proc. of Data Compression Conference, 21-31 March 2005.
  23. Faro S. and Lecroq T,"The exact online string matching problem: A review of the most recent results", ACM Comput. Survey, Article 13, 42 pages, February 2013.
  24. Ricardo A. Baeza-Yates and Gaston H. Gonnet,"A New Approach to Text Searching", In Communications of the ACM, pp. 74-82, Oct 1992.
  25. G. Navarro and M. Raffinot, "Fast and flexible string matching by combining bit-parallelism and suffix automata",ACM Journal. Experimental Algorithmics 1998.
  26. Hannu Peltola and Jorma Tarhio," Alternative Algorithms for Bit-Parallel String Matching", String Processing and Information Retrieval, Spire Springer, LNCS 2857, pp. 80-93, 2003.
  27. Longtao Hea, Binxing Fangaand Jie Sui," The wide window string matching algorithm" In the procd. Of Theoretical Computer Science of Elsevier, Vol. 332, pp. 391-404, 2005.
  28. L. Salmela, J. Tarhio, and J. Kytojoki, "Multi pattern string matching with q-grams", Journal of Experimental Algorithms, Volume 11, pp. 1-19, 2006.
  29. Branislav Durian, Jan Holub, Hannu Peltola and Jarma Tarhio,"Tuning BNDM with q-grams", In the proc. Of workshop on algorithm engineering and experiments, SIAM USA, pp. 29-37, 2009.
  30. Changsheng Miao, Guiran Chang and Xingwei Wang," Filtering Based Multiple String Matching Algorithm Combining q-Grams and BNDM", In proc. Of Fourth International Conference on Genetic and Evolutionary Computing, 2010.
Index Terms

Computer Science
Information Sciences

Keywords

String Matching Bit Parallelism Shift OR BNDM TNDM SBNDM LBNDM FBNDM BNDMq SBNDMq WW Algorithm.

Powered by PhDFocusTM