Approximate Pattern Matching with Grey Scale Values
Department of Computer Science,
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