Efficient two-dimensional compressed matching
- 2 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 279-288
- https://doi.org/10.1109/dcc.1992.227453
Abstract
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.Keywords
This publication has 5 references indexed in Scilit:
- Efficient pattern matching with scalingJournal of Algorithms, 1992
- Optimal parallel pattern matching in stringsInformation and Control, 1985
- A Technique for Extending Rapid Exact-Match String Matching to Arrays of More than One DimensionSIAM Journal on Computing, 1978
- Two dimensional pattern matchingInformation Processing Letters, 1977
- Fast Pattern Matching in StringsSIAM Journal on Computing, 1977