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

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

A Comparative Study of Wu Manber String Matching Algorithm and its Variations

by Vasudha Bhardwaj, Vikram Garg
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 132 - Number 17
Year of Publication: 2015
Authors: Vasudha Bhardwaj, Vikram Garg
10.5120/ijca2015907708

Vasudha Bhardwaj, Vikram Garg . A Comparative Study of Wu Manber String Matching Algorithm and its Variations. International Journal of Computer Applications. 132, 17 ( December 2015), 34-38. DOI=10.5120/ijca2015907708

@article{ 10.5120/ijca2015907708,
author = { Vasudha Bhardwaj, Vikram Garg },
title = { A Comparative Study of Wu Manber String Matching Algorithm and its Variations },
journal = { International Journal of Computer Applications },
issue_date = { December 2015 },
volume = { 132 },
number = { 17 },
month = { December },
year = { 2015 },
issn = { 0975-8887 },
pages = { 34-38 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume132/number17/23690-2015907708/ },
doi = { 10.5120/ijca2015907708 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:29:45.232720+05:30
%A Vasudha Bhardwaj
%A Vikram Garg
%T A Comparative Study of Wu Manber String Matching Algorithm and its Variations
%J International Journal of Computer Applications
%@ 0975-8887
%V 132
%N 17
%P 34-38
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
Abstract

String matching algorithms is become one of the most important topic in the computer science world. These algorithms are used in many real world problems like as scanning the threat in intrusion detection system, finding the pattern in text mining, match the similarity of the document in the plagiarism detection system, recognition in bio informatics and so on. String Matching Algorithms are broadly categorized into single pattern string matching and multiple pattern string matching algorithms. To get the faster solution of the problem most of the cases multiple pattern matching is the best choice. Aho-Corasick, Shift-OR, Robin Karp but Wu Manber Algorithm is better choice because it search the pattern faster(take less time) as well as occupies less space. This paper discus the various pit falls of the wu manber algorithm with their detailed explanation. Also discuss the various improved wu manber algorithm and comparison between these algorithms.

References
  1. Christian Charras and Thierry Lecroq,” Handbook of Exact String_Matching Algorithms”, Published in King’s college publication, Feb 2004.
  2. Alberto Apostolico and Zvi Galil,” Pattern Matching Algorithms” Published in Oxford University Press, USA, 1st edition, May 29, 1997.
  3. Fang Xiangyan, Xiong Tinggang, Ding Yidong and Youguang, ”The research and improving for multi-pattern string matching algorithm”, In the proc. of 2010 IEEE International Conference on Intelligent Computing and Intelligent Systems (ICIS), Vol. 1, pp. 266-270, Oct. 2010.
  4. Byung-joo Kim, Kim, “Kernel based intrusion detection system”, In the proc. of Fourth Annual ACIS International Conference on Computer and Information Science, pp. 13-18, 2005.
  5. 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.
  6. Alzahrani S.M. Salim N. and Abraham A., ”Understanding Plagiarism Linguistic Patterns, Textual Features, and Detection Methods”, In the proc. of IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews”, Vol. 42, Issue 2, pp. 133-149, march 2012.
  7. 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.
  8. 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-19 Dec. 2008.
  9. Qiong Zhang, Roger D. Chamberlain, Ronald S. Indeck, Benjamin M. West and Jason White,” Massively Parallel Data Mining Using Reconfigurable Hardware: Approximate String Matching”, In Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS’04), 2004.
  10. Marturana, F, Gianluigi Me and Tacconi, S,”A Case Study on Digital Forensics in the Cloud”, In the proc. of International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (Cyber C), pp. 111-116, 10-12 Oct. 2012.
  11. Jooyoung Lee, Sungkyung Un, and Dowon Hong,” Improving Performance in Digital Forensics”, In the Proc. of International Conference on Availability, Reliability and Security, 2009.
  12. BOYER, R. S. AND MOORE, J. S,”A fast string searching algorithm”, Communication of ACM 20, Vol. 10, pp. 762–772, 1977.
  13. Wu S. and U.Manber, “A Fast Algorithm for Multi-Pattern Searching,” Technical Report TR-94-17 Department of Computer Science, University of Arizona, Tucson, AZ, May 1994.
  14. 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.
  15. Chen Zhen and Wu Di, “Improving Wu-Manber: A Multi-pattern Matching Algorithm”, In the proc. of 2008 IEEE International Conference on Networking, Sensing and control (ICNSC), pp. 812 – 817, 6-8 April 2008.
  16. LiulingDai,”An aggressive algorithm for multiple string matching”Information Processing Letters, Volume 109, pp. 553–559, May 2009.
  17. Baojun Zhang, Xiaoping Chen, Xuezeng Pan, and Zhaohui Wu “High concurrence Wu-Manber Multiple Patterns Matching Algorithm”, Proceedings of the International Symposium on Information Proces, p.404,August 2009.
  18. 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.
  19. Yoon-Ho, Seung-Woo,”BLAST: B-Layered bad-character SHIFT tables for high-speed pattern matching”, Journal of Information Security, Institution of Engineering and Technology (IET), Volume 7, pp.195-202, sept.2013. MORRIS JR, J. H. AND PRAT, V. R.,”A linear pattern-matching algorithm”, Technical Report 40, University of California, Berkeley, 1970.
  20. 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.
  21. HORSPOOL, R. N,”Practical fast searching in strings”, In proc. Of Software Practical Exp, Vol. 10, 6, pp. 501–506, 1980.
  22. Alfred v. aho and margaret j. corasick,”efficient string matching: an aid to bibliographic search” communication of acm, vol. 18, june 1975.
  23. R. Baeza-Yates and G. Gonnet,“A new approach to text searching“, Communication of ACM, Vol. 35(10), pp. 74–82, 1992.
  24. G. Navarro,M. Raffinot, “Fast and flexible string matching by combining bit-parallelism and suffix automata”,ACM Journal. Experimental Algorithmics 2000.
  25. HannuPeltola and JormaTarhio, Alternative Algorithms for Bit-Parallel String Matching, String Processing and Information Retrieval, Spire 2003 Springer, LNCS 2857,pp. 80-93,2003. Branislav Durian, Jan Holub,HannuPeltola andJormaTarhio,” Tuning BNDM with q-Grams” In proc. of workshop on algorithm engineering and experiments SIAM USA, pp. 29-37, 2009
Index Terms

Computer Science
Information Sciences

Keywords

Multiple String Matching Wu Manber BLAST Algorithm Quick Wu Manber Improved Wu Manber.

Powered by PhDFocusTM