Abstract:
A pattern matching algorithm is used to find the presence of the pattern in a given block of data. Pattern matching is used to test whether things have a desired structure, to find relevant structure, to retrieve the aligning parts, and to substitute the matching part with something else. Sequence (or specifically text string) patterns are often described using regular expressions (i.e. backtracking) and matched using respective algorithms. Sequences can also be seen as trees branching for each element into the respective element and the rest of the sequence, or as trees that immediately branch into all elements. Pattern matching is useful in the field of text editing, highly computation intensive works like bioinformatics (pattern matching in biological sequence databases or amino acid sequence databases), networking (high-speed intrusion detection system), syntax analysis, operating systems, internet related searches to name a few.
Sequential pattern matching algorithms have almost reached their limits in terms of performance improvement. They are already linear in time complexity and the effective decrement in number of character comparisons is too less. In our work we first analyze most of the existing sequential and parallel pattern matching algorithms in terms of complexity, character comparisons and time of execution. Based on our analysis we try to parallelize the fastest sequential pattern matching algorithm — TVSBS to study the performance improvement. We use IBM Cell-Broadband Engine to implement our algorithm.
