ABSTRACT

Pattern matching is one of the important issues in the areas of network security and many others. The increase in network speed and traffic may cause the existing algorithms to become a performance bottleneck. Therefore, it is very necessary to develop more efficient pattern matching algorithm, in order to overcome troubles on performance. There are several algorithms in use, in which, some are with different methodology and other are with the improved methodology for the existing algorithms. In this paper, we are proposing a novel pattern matching algorithm, called, DP algorithm (Devaki – Paul algorithm). The algorithm works basing on some novel set of innovated rules, which will endorse the algorithm resulting in better performance and efficiency. In case of unsuccessful search, the DP algorithm has zero character comparisons, irrespective of the sizes of the text and pattern, provided if either the first or the last character was not present in the given input text. Whereas, the Booyer-Moore and Quick Search algorithms will do search as usual. The algorithm also doesn’t require any pre-processing phase, if the search is on the same given input text and with different patterns, provided the first and the last characters are same as in the case of first pattern. The algorithm was tested and validated and the results have proved that the performance of DP algorithm is better than BM algorithm (Boyer – Moore algorithm) and Quick Search algorithm. In case of tests with repeated character, its performance is greater than 1%~50% with BM and Quick Search algorithms. In case of tests with the English Text and Random Pattern, it’s greater than 33%~91% with BM and 37%~85% with Quick Search algorithms. In case of tests with the English Text and Random Pattern of an unsuccessful search, its performance is greater than BM and Quick Search algorithms with 100%, if either the first and/or the last character of the pattern in the given text were not present.