Two-dimensional pattern matching

In computer science, two-dimensional pattern matching is the problem of locating occurrences of a two-dimensional matrix of characters ("the pattern") in a bigger two-dimensional matrix ("the picture", or, in analogy with string searching, "the text").

The naïve solution

Assume given a pattern $P[m\times m]$ and a text $T[n\times n]$, where $m\leq n$. The simplest approach is to compare P against every sub-array of size </math>m\times m</math> in T. This algorithm has a worst-case time of $\Theta ((n-m+1)^{2}m^{2})$. It is usually assume that $m\leq n/2$, whence this can be written as $\Theta (n^{2}m^{2})$.

An automaton-based solution

We shall illustrate a more efficient solution (due essentially to Bird 1977) by means of an example. Suppose we have the following pattern and text

                 abaab
    aba          baaab
P = bab      T = abaab
    aba          babab
                 ababa

We first construct a Aho-Corasick automaton to search a linear text for occurrences of the columns of P. As a biproduct we obtain an identifier for every column, so that two identical columns get the same identifier: in our example, say the first (and third) columns are idntified by 0, and the middle column by 1.

Next, we run the automaton on the columns of T, obtaining (in linear time) an indication whenever one of the columns of P appears in T: in our example this will be a 3×5 matrix C as follow (a "-" marks an absence of a match):

                 abaab
    aba          baaab
P = bab      T = abaaa    C = 01---
    aba          babab        10--1
                 ababa        010-0

We now use the Knuth-Morris-Pratt Algorithm to search the rows of C for a pattern identical to P, i.e., 010. When we find one, we have idnetified an occurrence of P in T. Note that it is not necessary to keep all of C, or all of T, in memory; T can be read row by row, and from C one only needs to keep one row in memory---along with a row of states of the Aho-Corasick and the KMP automata.

The running time of this algorithm is $O(n^{2})$ if one ignores the dependence on the size of the alphabet, which exists in the Aho-Corasick algorithm. Taking this into account, the complexity is $O(n^{2}\log k)$ where k is the size of the alphabet.

More Efficient Solutions

The dependence on the size of the alphabet was removed by an $O(n^{2})$ algorith of Galil and Park.

See Also

• string searching algorithm

References

• Apostolico, Alberto (1999). "Chapter 13: General Pattern Matching". In Atallah (ed.). Algorithms and Theory of Computation Handbook. CRC Press. pp. 13–11. ISBN 0849326494.
• Bird, Richard S. (1977). "Two dimensional pattern matching". Information Processing Letters. 6 (5): 168–170.
• Galil, Zvi; Park, Kunsoo (1996). "Alphabet-independent two-dimensional witness computation". SIAM Journal on Computing. 25 (5): 907–935.