Designing a Sytolic Matcher for 2-Dim Patterns
Mohammad Kheyrandish, Mohammad Reza Babaei Mosleh, Saeid Setayeshi, Mohammad Golshahi · 2009
Pattern matching includes verifying the existence of a pattern in a given reference set. It has exact and approximate matching types. Most important algorithms for pattern matching are Brute-Force, Morris-Pratt, Boyer-Moore, Wu-Manber, Baeza-Yates-Navarro, Myers and Dynamic Programming Algorithm. Systolic Array is a set of simple processing cells that are placed beside each other based on a regular pattern and there are local communications between them. This paper has presented systolic pattern matchers that can examine the matching of pattern Pl.m and text matrix Tn.q in a n.(q+m-1) and n.l time,respectively, whereas the required time for 2-dim pattern matching algorithm on computer is O(n.q.l.m).