Efficient Multiple Pattern Matching Algorithm
Based on BMH: MP-BMH
Akhtar Rasool1, Gulfishan Firdose Ahmed2, Raju Barskar3, and Nilay Khare1
1Department of Computer Science and Engineering, Maulana Azad National
Institute of Technology, India
2Department of Computer Science, College of Agriculture, India
3Department of Computer Science and Engineering, University Institute of
Technology RGPV, India
Abstract: String matching is playing a
key role in a wide range of applications in the information computing. Due to
its importance, large numbers of different algorithms have been developed over
the last 50 years. There are various standards of single and multiple pattern
string matching algorithms like Boyer-Moore (BM), Boyer-Moore-Horspool (BMH), Aho-Corasick etc.
Multiple pattern string matching is very useful in real world applications.
Standard benchmark multiple pattern algorithm Aho-Corasick and many other
multiple pattern string matching algorithms are not memory and time efficient
for wider length and large number of patterns set on large text data set
because they are using the concept like DFA and require full scan of text data.
Many string matching tools which are currently popular for string matching are
based on these algorithms. Using the bad character principle of BMH, a method
for multiple pattern string matching is being developed. Using this method a
time and memory efficient exact multiple pattern string matching algorithm
Multiple Pattern BMH (MP-BMH) is proposed. Unlike Aho-Corasick, the proffered
MP-BMH algorithm provides skipping of unnecessary matching of characters in
text while searching like BMH Algorithm. It also provides the skipping of
characters in patterns using the similarity between patterns. Along with the
shifts while searching, this algorithm also provides shrewd switches among the
patterns for efficacious matching.In this paper, the aforesaid
method, MP-BMH algorithm with its time, memory and experimental analysis are
described.
Keywords: String matching;
multiple pattern string matching, Boyer-Moore BM,BMH, MP-BMH.
Received January 8, 2017; accepted January 16, 2018