###
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