二维模式近似匹配的快速算法

A Fast Approach to TwoDimensional Pattern Matching

给定一个大小为ｎ×ｎ的文本Ｔ和一个大小为ｍ×ｍ的模板Ｐ，如果文本Ｔ中存在一个ｍ×ｍ的子块与模板Ｐ能够逐点匹配，称为精确匹配。如果最多有ｋ个元素不同，称为带有最多ｋ个误差的近似匹配。对于精确匹配，本文给出了一个时间复杂性为Ｏ（ｎ２ｌｏｇ｜∑｜）的算法，∑＝｛ａ１，２，…，ａ｜∑｜｝，是模板的字符集。对于近似匹配，快速算法分为两步：（１）预选。利用精确匹配算法找出能精确匹配的ｓ×ｓ（０≤ｓ≤ｍ）子块，得到ｈ个候选的对准点；（２）验证。把模板对准候选点，逐点比较，以确定不相同的元素是否不超过ｋ个。近似匹配的时间复杂性为Ｏ（ｎ２ｌｏｇ｜∑｜＋ｈｍ２）。

Given a text of size n×n and a pattern of size m×m, the exactmatching is to find all occurrence of the pattern in the text, while the approximatematching is to find all the location of m×m blocks in the text that differ by at most k mismatches. We present a new approach for exactmatching, which runs in O(n2log|∑|),∑={a1,a2,…,a|∑|} is the alphabet of the pattern, and for approximatematching , in O(n2log|∑|)+hm2), which consists of two stages. The first stage is to preselect h subblocks of size s×s(0≤s≤m) that exactly match the pattern. And the second stage of verification compares the blocks containing these h subblocks to determine if the mismatches is no more than k.