Alphabet-independent and scaled dictionary matching

The rapidly growing need for analysis of digitized images in multimedia sys tems has led to a variety of interesting problems in multidimensional patte rn matching. One of the problems is that of scaled matching, finding all ap pearances of a pattern In a text in all sizes. Another important problem is dictionary matching. a quick search through a dictionary of preprocessed p atterns in order to find all dictionary patterns that appear in the input t ext. In this paper we provide a simple algorithm for two-dimensional scaled matching. Our algorithm is the first linear-time alphabet-independent scal ed matching algorithm. Its running time is O(\T\), where \T\ is the text si ze, and is independent of \Sigma\, the size of the alphabet. The main idea behind our algorithm is to identify and exploit a scaling-invariant propert y of patterns. (I)ur technique generalizes to produce the first known algor ithm for scaled dictionary matching. We can find all appearances of all dic tionary patterns that appear in the input text in any discrete scale. The t ime bounds of our algorithm are equal to the currently known exact (no scal ing) two-dimensional dictionary; matching algorithms. (C) 2000 Academic Pre ss.