Efficient two-dimensional compressed matching
Efficient two-dimensional compressed matching
复制标题
高效的二维压缩匹配
DOI：
10.1109/dcc.1992.227453
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
Gary Benson
中科院分区：
文献类型：
--
作者：
A. Amir;Gary Benson
众所周知，数字化图像非常耗费空间。然而，通常可以利用图像中的规律性来减少必要的存储区域。因此，许多系统以压缩形式存储图像。作者建议，除了传统的节省空间的作用外，压缩还可以作为一种节省时间的工具。它们引入了一种新的模式匹配范例--压缩匹配。文本数组T和图案数组P以压缩形式c(T)和c(P)给出。它们寻找P在T中的所有出现，而不解压缩T。这实现了搜索时间与未压缩文本mod T mod的大小次线性。它们表明，对于二维游程压缩，存在一个O(mod c(T)mod log mod P mod+mod P mod)或几乎最优的算法。该算法使用了一种新的多维模式匹配技术，即二维周期分析。
Digitized images are known to be extremely space consuming. However, regularities in the images can often be exploited to reduce the necessary storage area. Thus, many systems store images in a compressed form. The authors propose that compression be used as a time saving tool, in addition to its traditional role of space saving. They introduce a new pattern matching paradigm, compressed matching. A text array T and pattern array P are given in compressed forms c(T) and c(P). They seek all appearances of P in T, without decompressing T. This achieves a search time that is sublinear in the size of the uncompressed text mod T mod . They show that for the two-dimensional run-length compression there is a O( mod c(T) mod log mod P mod + mod P mod ), or almost optimal algorithm. The algorithm uses a novel multidimensional pattern matching technique, two-dimensional periodicity analysis.<<ETX>>