We address the problem of approximate string matching in two dimensions, that is, to find a pattern of size m*m in a text of size n*n with at most k errors. ALthough the problem can be solved using dynamic programming in time O(m sup 2n sup 2), this is in general too expensive for small k . So we design a filtering algorithm which avoids verifying most of the text with dynamic programming. This filter is based on a one-dimensional multi-pattern approximate search algorithm. The average complexity of our resulting algorithm is O(n sup 2klog m/m sup 2) for k < m(m+1)/(5 log m), which is optimal and matches the best previous result which allows only subbstitutions. For higher error levels, we present an algorithm with time complexity O(n sup 2k/w delta sup 1/2). This algorithm works for k < m(m+1)(1-e/delta sup 1/2), where e=2.178 ..., a limit whihc is not possible to improve. These are the firt good expected-case algorithms for the problem. Our algorithms work also for rectangular patterns and rectangular text and can even be extended to the case where each row in the pattern and the text has a different length.
展开▼
