Approximate Pattern Matching with Grey Scale Values

Tadao TAKAOKA
Department of Computer Science, Ibaraki University, Hitachi, Ibaraki 316, Japan.
takaoka@cis.ibaraki.ac.jp

Abstract

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