Two-dimensional periodicity and matching algorithms
Gary Benson · 1992
String matching is rich with a variety of algorithmic tools. In contrast, multidimensional matching has a rather sparse set of techniques. This work represents a new algorithmic technique for two-dimensional matching: periodicity analysis. Its strength lies in the fact that it is inherently two-dimensional. Periodicity in strings has recently been used to solve string matching problems. Multidimensional periodicity, though, is not as simple as it is in strings and was not formally studied or used in pattern matching. In this work, I define and analyze two-dimensional periodicity in rectangular arrays. I show that, based on the ability of an array to overlap itself, there are exactly four categories of periodic arrays: non-periodic, lattice-periodic, line-periodic and radiant-periodic. I present serial and parallel algorithms that find all locations where an overlap originates. In addition, for any other location my algorithms find a witness providing that the array does not self overlap. For an array P, the serial algorithm runs in time $O(\vert P\vert)$ (linear time) when the alphabet size is finite, and $O(\vert P\vert\log\vert P\vert)$ otherwise. The parallel algorithm runs in time $O(\log\vert P\vert)$ using $O(\vert P\vert)$ CRCW processors. The definition of two-dimensional periodicity has proven to be robust as illustrated by its use in solving the following two problems: (1) Compressed Matching. A text array T and pattern array P are given in compressed forms $c(T)$ and $c(P)$. We seek all appearances of P in T, without decompressing T. I show using periodicity analysis, that for the two-dimensional run-length compression there is a $O(\vert c(T)\vert\log\vert P\vert + \vert P\vert)$, or almost optimal matching algorithm. (2) Two-Dimensional Exact Matching. A text array T and a pattern array P are given. We seek all appearances of P in T. Previous solutions to this problem had a logarithmic dependence on the alphabet size. In the worst case, (unbounded alphabet size), these algorithms run in time $O(\vert T\vert\log\vert P\vert)$ with $O(\vert P\vert\log\vert P\vert)$ preprocessing. I show using periodicity analysis, that the time for the text scanning can be reduced to $O(\vert T\vert)$, independent of the alphabet size.