MULTIPLE STRING PATTERN MATCHING ALGORITHMS

Abstract

Multiple string pattern matching is an approach to find all occurrences of a set of patterns in given text. With evolution of computation capacity along with storing capacity, we are in quest of analysing large data sets for search of information in terms of patterns. Efficiency of searching algorithms depends on development of an accurate & precise shift table. In case of a mismatch between text and pattern, shift table determines maximum length of part of text which can be skipped without missing any pattern match. However, with increase in size of data to be searched, there is a constant urge to reduce search time. Thus, we need a faster searching algorithm. This study extends Boyer Moore concept to cultivate a new shift table algorithm which works on multiple variable length patterns and can cohesively be used with various searching techniques. Run-time complexity of the presented algorithm is O(N) where N denotes sum of lengths of all variable length patterns. This study also presents a new hashing based algorithm for fast search of multiple variable length patterns in large data sets. It can accommodate patterns which come up during search time. Furthermore, its speed enhances as the minimum pattern length P increases for data set of length n taking O(n/P) time during search. Further, idea of clustering the pattern set prior to searching phase is proposed which experimentally speed up search time by factor of 4 in concerned case study. This case study consists of search set with more than 420,000 characters with number of patterns ranging from 50 to 100 and pattern length varying from 4 to 26. It also identifies various factors which effects searching time and establishes mathematical relationship among them.