Efficient multiple pattern matching algorithm based on BMH : MP-BMH

Abstract EN

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.