Approximate Pattern Matching with Grey Scale Values

Department of Computer Science, Ibaraki University, Hitachi, Ibaraki 316, Japan.


We design an efficient algorithm for approximate pattern matching with grey scale values. The grey scale values range over interval $[0,R]$ where $R$ is a positive real number and the error bound for matching is measured by $kR$ where $k$ is a non-negative integer. Then we show that our algorithm solves this problem for the one-dimensional problem with $O(kn\log m/m)$ expected time, which is sublinear, where $m$ and $n$ are the sizes of pattern and text. For the two-dimensional problem, the expected time is $O(kn^2\log m/m^2)$ where $m^2$ and $n^2$ are the sizes of pattern and text. The results are useful for time series analysis and graphics where grey scale matching is more suitable than character matching.
Conference Home Page