Years and Authors of Summarized Original Work
2003; Amir, Landau, Sokol
Problem Definition
Letc be a given compression algorithm, and let c(D) be the result of c compressing data D. The compressed search problem with compression algorithm c is defined as follows.
Input: Compressed~text \( { c(T) } \) and~pattern P.
Output: All locations in T where pattern P occurs.
A compressed matching algorithm is optimal if its time complexity is \( { O(|c(T)|) } \).
Although optimality in terms of time is always important, when dealing with compression, the criterion of extra spaceis perhaps more important (Ziv, Personal communication, 1995). Applications employ compression techniques specifically because there is a limited amount of available space. Thus, it is not sufficient for a compressed matching algorithm to be optimal in terms of time, it must also satisfy the given space constraints. Space constraints may be due to limited amount of disk space (e.g., on a server), or they may be related...
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Recommended Reading
Amir A, Benson G (1992) Efficient two dimensional compressed matching. In: Proceeding of data compression conference, Snow Bird, pp 279–288
Amir A, Benson G (1992) Two-dimensional periodicity and its application. In: Proceeding of 3rd symposium on discrete algorithms, Orlando, pp 440–452
Amir A, Benson G (1998) Two-dimensional periodicity and its application. SIAM J Comput 27(1):90–106
Amir A, Benson G, Farach M (1992) The truth, the whole truth, and nothing but the truth: alphabet independent two dimensional witness table construction. Technical Report GITCC-92/52, Georgia Institute of Technology
Amir A, Benson G, Farach M (1994) An alphabet independent approach to two dimensional patternmatching. SIAM J Comput 23(2):313–323
Amir A, Benson G, Farach M (1997) Optimal two-dimensional compressed matching. J Algorithms 24(2):354–379
Amir A, Benson G, Farach M (1998) Optimal parallel two dimensional text searching on a crew pram. Inf Comput 144(1):1–17
Amir A, Landau G, Sokol D (2003) Inplace 2D matching in compressed images. J Algorithms 49(2):240–261
Amir A, Landau G, Sokol D (2003) Inplace run-length 2D compressed search. Theory Comput Sci 290(3):1361–1383
Berman P, Karpinski M, Larmore L, Plandowski W, Rytter W (1997) On the complexity of pattern matching for highly compressed two dimensional texts. In: Proceeding of 8th annual symposium on combinatorial pattern matching (CPM 97). LNCS, vol 1264. Springer, Berlin, pp 40–51
Crochemore M, Galil Z, Gasieniec L, Hariharan R, Muthukrishnan S, Park K, Ramesh H, Rytter W (1993) Parallel two-dimensional pattern matching. In: Proceeding of 34th annual IEEE FOCS, pp 248–258
Galil Z, Park K (1996) Alphabet-independent two-dimensional witness computation. SIAM J Comput 25(5):907–935
Hennessy JL, Patterson DA (1996) Computer architecture: a quantitative approach, 2nd edn. Morgan Kaufmann, San Francisco
Klein ST, Shapira D (2005) Compressed pattern matching in JPEG images. In: Proceeding Prague stringology conference, pp 125–134
Klein ST, Wiseman Y (2003) Parallel huffman decoding with applications to JPEG files. Comput J 46(5):487–497
Park K, Galil Z (1992) Truly alphabet-independent two-dimensional pattern matching. In: Proceeding 33rd IEEE FOCS, pp 247–256
Régnier M, Rostami L (1993) A unifying look at d-dimensional periodicities and space coverings. In: 4th symposium on combinatorial pattern matching, p 15
Vishkin U (1985) Optimal parallel pattern matching in strings. In: Proceeding 12th ICALP, pp 91–113
Welch TA (1984) A technique for high-performance data compression. IEEE Comput 17:8–19
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer Science+Business Media New York
About this entry
Cite this entry
Amir, A. (2016). Multidimensional Compressed Pattern Matching. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, New York, NY. https://doi.org/10.1007/978-1-4939-2864-4_246
Download citation
DOI: https://doi.org/10.1007/978-1-4939-2864-4_246
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4939-2863-7
Online ISBN: 978-1-4939-2864-4
eBook Packages: Computer ScienceReference Module Computer Science and Engineering