Comparative analysis of Pattern Matching methodologies

摘要

Pattern Matching is an extensively studied problem in computer science, mainly due to its direct applications to diverse fields like text processing, speech processing, computational biology, chemistry, etc. Also, the amount of data stored in the computer systems these days is increasing at an exponential rate. Pattern matching algorithms are also basic components used in implementations of practical software existing under most operating systems. Hence, it becomes essential to design algorithms that can work efficiently on such huge amounts of data. The pattern matching problem basically consists of finding all occurrences of a pattern in the given text, over some alphabet. Here, we present the experimental results of some of the recently designed pattern matching algorithms and compare them from a practical point of view. As it turns out, the performance of the algorithms depends on both the alphabet size and pattern lengths.