On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts

摘要

We consider the complexity of problems related to two-dimensional texts (2D-texts) described succinctly. In a succinct description, larger rectangular subtexts are defined in terms of smaller parts in a way similar to that of Lempel–Ziv compression for 1D-texts, or in strings with shortened descriptions as in (Nordic J. Comput.4 (1997) 172–186), or in hierarchical graphs described by context-free graph grammars. A given 2D-text T with many internal repetitions can have a hierarchical description which may be exponentially smaller and which can be given as an input for a pattern-matching algorithm which gives information about T. Such a hierarchical description is given in terms of a straight-line program, or SLP (see Nordic J. Comput.4 (1997) 172–186) or, equivalently, of a 2D grammar. We consider compressed pattern matching, where the input consists of a 2D-pattern P and a hierarchical description of a 2D-text T, and fully compressed pattern matching, where the input consists of hierarchical descriptions of both the pattern P and the text T. For 1D strings, there exist polynomial-time deterministic algorithms for these problems for similar types of succinct text descriptions (J. Comput. System Sci.52 (2) (1996) 299–307; “Proceedings of the 27th Annual Symposium on the Theory of Computing,” pp. 703–712; “Proceedings of the 5th Scandinavian Workshop on Algorithm Theory,” Springer-Verlag, Berlin, 1996; Nordic J. Comput.4(2) (1997), 172–186). We show that the complexity dramatically increases in a 2D setting. For example, compressed 2D-matching is NP-complete, fully compressed 2D-matching is ΣP2-complete, and testing a given occurrence of a 2D compressed pattern is co-NP-complete. On the other hand, we give efficient algorithms for the related problems of randomized equality testing and testing for a given occurrence of an uncompressed pattern. We also show the surprising fact that the compressed size of a subrectangle of a compressed 2D array can grow exponentially, unlike the 1D case.