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 m2. The best compression that the 2D-LZ technique can obtain for a file of size m2 is O(m). The time for performing the search is O(n2) and the preprocessing time is O(m3). Our algorithm is general in the sense that it can be used for any 2D compression which can be sequentially decompressed in small space.
展开▼
机译：在[1]中定义的压缩匹配问题是在压缩文本中查找所有出现的模式的问题。在本文中，我们讨论了Lempel-Ziv压缩图像中的二维压缩匹配问题。给定（未压缩）大小 m × m 的模式，并给出（未压缩）大小 n × n ，都是，都是2D-LZ压缩形式，我们的算法可以找到 T 中所有 P 的出现。该算法是强烈就位的，也就是说，所使用的额外空间量与大小为 m 2 的模式的最佳压缩程度成正比。 。对于大小为 m 2 的文件，2D-LZ技术可获得的最佳压缩为 O （ m ）。执行搜索的时间为 O （ n 2 ），预处理时间为 O （ m 3 ）。从某种意义上说，我们的算法是通用的，它可以用于任何2D压缩，并且可以在较小的空间中依次进行解压缩。
展开▼
