Efficient Multiple Pattern Matching Algorithm Based on BMH: MP-BMH
Journal: The International Arab Journal of Information Technology (Vol.16, No. 6)Publication Date: 2019-11-01
Authors : Akhtar Rasool; Gulfishan Firdose Ahmed; Raju Barskar; Nilay Khare;
Page : 1121-1130
Keywords : String matching; multiple pattern string matching; Boyer-Moore BM; BMH; MP-BMH.;
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.
Other Latest Articles
- Comparative study of the outcome of tubed versus tubeless percutaneous nephrolithotomy
- An Ontology Alignment Hybrid Method Based on Decision Rules
- The relationship between overhydration, increased oxidative stress and peritoneal dialysis adequacy
- FBMT: Fuzzy Based Merkle Technique for Detecting and Mitigating Malicious Nodes in Sensor Networks
- Rating score of renal medical care in Ukraine provinces: 2018
Last modified: 2019-11-11 22:06:02