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").{{sfnp|Apostolico|1999}}

The naïve solution

Assume given a pattern $P[m\times m]$ and a text $T[n\times n]$ , where $m\le n$ .

The simplest approach is to compare P against every sub-array of size m\times m in T. This algorithm has

a worst-case time of $\Theta((n-m+1)^2m^2)$ . It is usually assume that $m\le n/2$ , whence this can be written

as $\Theta(n^2m^2)$ .

An automaton-based solution

We shall illustrate a more efficient solution (due essentially to {{Harvnb|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.

Footnotes

References

{{cite book

| last = Apostolico

| first = Alberto

| editor = Atallah

| title = Algorithms and Theory of Computation Handbook

| chapter = Chapter 13: General Pattern Matching

| publisher = CRC Press

| year = 1999

| pages = 13-11

| isbn = 0849326494

}}

{{Cite journal

| last = Bird

| first = Richard S.

| title = Two dimensional pattern matching

| journal = Information Processing Letters

| volume = 6

| issue = 5

| pages = 168-170

| date =

| year = 1977

| doi =

| pmid =

| url =

}}

{{Cite journal

| last1 = Galil

| first1 = Zvi

| last2 = Park

| first2 = Kunsoo

| title = Alphabet-independent two-dimensional witness computation

| journal = SIAM Journal on Computing

| volume = 25