Dynamic programming algorithms for picture comparison |
| |
Authors: | Michael S Waterman |
| |
Institution: | Departments of Mathematics and Biological Sciences, University of Southern California, Los Angeles, California 90089-1113 U.S.A. |
| |
Abstract: | Two-dimensional arrays can be compared by a generalization of dynamic programming algorithms for string comparison. Earlier algorithms have computational complexity O(N6) for comparison of two N × N arrays. The computational complexity is reduced to O(N4) in general and O(N2) algorithms are pointed out for the range limited case. An example is given to illustrate the lack of knowledge of mathematical properties of these algorithms. The problem of finding an algorithm to compute the minimum number of insertions, deletions, and substitutions to transform one array into another remains open. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|