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

Efficient Wu Manber String Matching Algorithm for Large Number of Patterns

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/ijca2015907707

Vasudha Bhardwaj, Vikram Garg . Efficient Wu Manber String Matching Algorithm for Large Number of Patterns. International Journal of Computer Applications. 132, 17 ( December 2015), 29-33. DOI=10.5120/ijca2015907707

@article{ 10.5120/ijca2015907707,
author = { Vasudha Bhardwaj, Vikram Garg },
title = { Efficient Wu Manber String Matching Algorithm for Large Number of Patterns },
journal = { International Journal of Computer Applications },
issue_date = { December 2015 },
volume = { 132 },
number = { 17 },
month = { December },
year = { 2015 },
issn = { 0975-8887 },
pages = { 29-33 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume132/number17/23689-2015907707/ },
doi = { 10.5120/ijca2015907707 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:29:44.540125+05:30
%A Vasudha Bhardwaj
%A Vikram Garg
%T Efficient Wu Manber String Matching Algorithm for Large Number of Patterns
%J International Journal of Computer Applications
%@ 0975-8887
%V 132
%N 17
%P 29-33
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
Abstract

String matching is one of the most important concept used in computer science in various real life applications like as Intrusion detection system, Data mining, Plagiarism detection system. There are many string matching algorithms which help to find pattern from the text. These algorithms are categorized in single string matching and multiple string matching. The Wu-Manber (WM) algorithm is multiple patterns algorithm which is the finest string matching algorithm. The performance of WM depends on various table build in pre processing phase these are prefix table, shift table and hase table. We introduce a new algorithm namely the Efficient Wu Manber algorithm (EWM) algorithm which is advance version of Wu Manber algorithm with respect to time. Efficient Wu-Manber Algorithm eliminate the prefix table which is unused most of the cases in wu manber, construct two shift table instead of single shift table and uses nonlinear data structure i.e. AVL tree instead of linear data structure i.e. linked list used in WM in Hash table, which reduce the traversed number of nodes to find exact match. The experimental results and analysis show that EWM algorithm has better performance as compare to WM and its existing improved algorithm and also better from various string matching tools.

References
  1. Christian Charras and Thierry Lecroq,” Handbook of Exact String_Matching Algorithms”, Published in King’s college publication, Feb 2004.
  2. 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.
  3. 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.
  4. Boyer R S and Moore J S,”A fast string searching algorithm”, Communication of ACM 20, Vol. 10, pp. 762–772, 1977.
  5. Horspool R N,”Practical fast searching in strings”, In proc. Of Software Practical Exp, Vol. 10, 6, pp. 501–506, 1980.
  6. Alfred v aho and Margaret j corasick,”efficient string matching: an aid to bibliographic search” communication of acm, vol. 18, June 1975.
  7. 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.
  8. 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).
  9. 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.
  10. R. M. Karp and M. O. Rabin, “Efficient randomized pattern-matching algorithms,” In: (2nd ed.), Tech. Rept. 31-81, Aiken Computer Lab, Harvard University, Cambridge, MA, 1981.
  11. 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.
  12. D.M. Sunday, “A Very Fast Substring Search Algorithm”, Communications of the ACM, Vol. 33, 8, pp. 132-142, 1990.
  13. 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.
  14. 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.
Index Terms

Computer Science
Information Sciences

Keywords

Wu-Manber String Matching Single pattern matching Multiple pattern matching Boyer Moore KMP Advance Wu Manber.

Powered by PhDFocusTM