Inplace 2D matching in compressed images

ABSTRACT

The compressed matching problem, defined in [1] is the problem of finding all occurrences of a pattern in a compressed text. In this paper we discuss the 2-dimensional compressed matching problem in Lempel-Ziv compressed images. Given a pattern of (uncompressed) size m × m, and a text of (uncompressed) size n × n, both in 2D-LZ compressed form, our algorithm finds all occurrences of P in T. The algorithm is strongly inplace, that is, the amount of extra space used is proportional to the best possible compression of a pattern of size m². The best compression that the 2D-LZ technique can obtain for a file of size m² is O(m). The time for performing the search is O(n²) and the preprocessing time is O(m³). Our algorithm is general in the sense that it can be used for any 2D compression which can be sequentially decompressed in small space.

REFERENCES

• 1: A. Amir and G. Benson. Efficient two dimensional compressed matching. Proc. of Data Compression Conference, Snow Bird, Utah, pages 279--288, Mar 1992.
• 2: Amihood Amir , Gary Benson, Two-Dimensional Periodicity in Rectangular Arrays, SIAM Journal on Computing, v.27 n.1, p.90-106, Feb. 1998 [doi>10.1137/S0097539795298321]
• 3: A. Amir, G. Benson, and M. Farach. Let sleeping files lie: Pattern matching in Z-compressed files. Technical Report GIT-CC-93/42, Georgia Institute of Technology, June 1993.
• 4: Amihood Amir , Gary Benson , Martin Farach, An Alphabet Independent Approach to Two-Dimensional Pattern Matching, SIAM Journal on Computing, v.23 n.2, p.313-323, April 1994 [doi>10.1137/S0097539792226321]
• 5: Amihood Amir , Gary Benson , Martin Farach, Let sleeping files lie: pattern matching in Z-compressed files, Journal of Computer and System Sciences, v.52 n.2, p.299-307, April 1996 [doi>10.1006/jcss.1996.0023 ]
• 6: Amihood Amir , Gary Benson , Martin Farach, Optimal two-dimensional compressed matching, Journal of Algorithms, v.24 n.2, p.354-379, Aug. 1997 [doi>10.1006/jagm.1997.0860 ]
• 7: Amihood Amir , Gad M. Landau , Dina Sokol, Inplace run-length 2d compressed search, Theoretical Computer Science, v.290 n.3, p.1361-1383, 3 January 2003 [doi>10.1016/S0304-3975(02)00041-5]
• 8: Piotr Berman , Marek Karpinski , Lawrence L. Larmore , Wojciech Plandowski , Wojciech Rytter, On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts, Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching, p.40-51, June 30-July 02, 1997
• 9: Martin Farach , Mikkel Thorup, String matching in Lempel-Ziv compressed strings, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.703-712, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225288]
• 10: Zvi Galil , Kunsoo Park, Alphabet-Independent Two-Dimensional Witness Computation, SIAM Journal on Computing, v.25 n.5, p.907-935, Oct. 1996 [doi>10.1137/S0097539792241941]
• 11: Leszek Gasieniec , Marek Karpinski , Wojciech Plandowski , Wojciech Rytter, Randomized Efficient Algorithms for Compressed Strings: The Finger-Print Approach (Extended Abstract), Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, p.39-49, June 10-12, 1996
• 12: Leszek Gasieniec , Wojciech Rytter, Almost Optimal Fully LZW-Compressed Pattern Matching, Proceedings of the Conference on Data Compression, p.316, March 29-31, 1999
• 13: D.E. Knuth, J.H. Morris, and V.R. Pratt. Fast pattern matching in strings. SIAM J. Computing, 6:323--350, 1977.
• 14: A. Lempel and J. Ziv. Compression of two-dimensional images. In Z. Galil A. Apostolico, editor, Combinatorial Algorithms on Words, volume 12, pages 141--154. NATO ASI Series F, 1985.
• 15: W. Plandowski L. Gasieniec and W. Rytter. Constant-space string matching with smaller number of comparisons: sequential sampling. In Proc. 6th Annual Symposium on Combinatorial Pattern Matching (CPM 95). LNCS, Springer, 1995.
• 16: N. Memon, D. Neuhoff, and S. Shende. An analysis of some common scanning techniques for lossless image coding, http://citeseer.nj.nec.com/23495.html.
• 17: J. Ziv. personal communication. 1995.
• 18: J. Ziv and A. Lempel. Compression of individual sequences via variable rate coding. IEEE Trans. on Information Theory, IT-24:530--536, 1978.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  G. Mathematics of Computing
  G.m MISCELLANEOUS

General Terms:
Algorithms, Theory