Multiple Pattern String Matching Methodologies: A Comparative Analysis
Zeeshan Ahmed Khan, Rajesh Kumar Pateriya, Maulana Azad · 2012
Abstract—String matching algorithms in software applications like virus scanners (anti-virus) or intrusion detection systems is stressed for improving data security over the internet. String-matching techniques are used for sequence analysis, gene finding, evolutionary biology studies and analysis of protein expression. Other fields such as Music Technology, Computational Linguistics, Artificial Intelligence, Artificial Vision, have been using string matching algorithm as their integral part of theoretical and practical tools. There are various problems in string matching appeared as a result of such continuous, exhaustive use, which in turn were promptly solved by the computer scientists. The more practical solutions to the real world problems can be solved by the multiple pattern string matching algorithms. String Matching Algorithms like Aho-Corasick, Commentz-Walter, Bit parallel, Rabin-Karp, Wu-Manber etc. are to be focused in this paper. Aho-Corasick algorithm is based on finite state machines (automata). Commentz Walter algorithm is based on the idea of Knutt-Morris-Pratt and finite state machines. Bit parallel algorithm like shift-or makes use of wide machine words (CPU registers) to parallelize the work. Rabin-Karp uses hashing to find any one of a set of pattern strings in a text. Wu-Manber looking text in blocks instead of one by one character combining idea of Aho-Corasick and Boyer-Moore. Each algorithm has certain advantages and disadvantages. This paper presents the comparative analysis of various multiple pattern string matching algorithms. A comparison of Aho-Corasick, Commentz-Walter, Bit-Parallel(Shift-OR), Rabin-Karp, Wu-Manber etc. type of string matching algorithms is presented on different parameters.