二维模式（矩阵）匹配（Rabin-Karp算法推广到二维）[转]

本文着重讨论由Rabin-Karp算法推广到二维来解决二维模式匹配问题的算法。

问题：

在一个n₁*n₂的二维字符组成中搜寻一个给定的m₁*m₂的模式。参考《算法导论》习题32.2-3.

分析：

1. 首先简单介绍一下Rabin-Karp算法

Rabin-Karp算法是一种字符串匹配算法，它的主要思想是预先计算出模式串的hash值，匹配时再计算出待匹配子串的hash值，直接比较模式串和当前子串的hash值是否相等即可判断是否匹配。

为了便于说明，以下以数字串为例（字符串的每个字符都是一个十进制的数字，比如字符串31415）。已知一个模式P[1..m]，设p表示其相应的 十进制数的值。类似的，对于给定的文本T[1..n]，用ts表示其长度为m的子字符串T[s+1..s+m](s=0,1,..,n-m)相应的十进制 数的值。很显然的，如果T[s+1..s+m]与模式P[1..m]匹配，那么t_s一定等于p，相反的，如果t_s=p，那么T[s+1..s+m]一定与P[1..m]匹配。如果能够在O(m)时间内计算出p的值，并在总共O(n-m+1)的时间内计算出所有ts的值，那么通过把p值与每个t_s值进行比较，就能够在O(m)+O(n-m+1)=O(n)的时间内，找到所有的匹配。

RK算法通过霍纳法则(Horner’s Rule)在O(m)时间内计算出p的值：

p=P[m]+10(P[m-1]+10(P[m-2]+…+10(P[2]+10P[1])..))

同理可以在O(m)时间内计算出t₀的值。

又因为

t_s+1=10[t_s-10^m-1T[s+1])+T[s+m+1]

所以可以在常数时间内根据t_s计算出t_s+1

例如，如果m=5，ts=12345，假定下一位是6，去掉高位数字1，再加入低位数字6，就得到：

t_s+1=10*(12345-10000*1)+6=23456

因此，Rabin-Karp算法能够用O(m)的预处理时间和O(n-m+1)的匹配时间，找出模式P[1..m]在文本T[1..n]中的所有出现。

这个过程唯一的问题是p和t_s的值可能太大，RK算法是通过模等价来处理。实际计算出来的p和t_s的值都是模q后的值，在匹配时如果p和t_s值相等，串还未必匹配，这时候还需要通过朴素的比较这两个串来测试。本文不考虑这个，有兴趣的可以参考算法导论。

另外，这个例子是基于数字串的，对于一般情况，可以假定每个字符都是基数为d的表示法中的一个字符，这时上面2个计算公式中的10要换成相应的d。

2. 推广到二维

首先，来看模式矩阵。如果把m₂列中的每一列都看做一个整体，那么他们每一个都是一个一维的串，可以分别计算出hash值（使用霍纳法则），这样模式矩阵就成了一个一维的长度为m₂的模式串。

然后，对大矩阵的前m₁行，用同样的方法能得到一个长度为n₂的串。

这样，在大矩阵的前m₁行中寻找模式矩阵，就转化成了一维的字符串匹配问题。（这里使用一维的串匹配算法就能解决，比如KMP）

最后，用同样的方法，在大矩阵的第2到第m₁+1行，第3到m₁+2行。。。都可以用同样的方法匹配。

这里的关键是，每次匹配时，转化后的一维串可以通过上次的串直接计算出来。（类似于Rabin-Karp由t_s可以在常数时间内计算出t_s+1）

源码- JAVA

01    public class StringMatch2D { 

02     

03        public static void main(String[] args) { 

04            char[][] text = { 

05                               { 'a', 'b', 'a', 'b', 'a' },

06                               { 'a', 'b', 'a', 'b', 'a' },

07                               { 'a', 'b', 'b', 'a', 'a' },

08                               { 'a', 'b', 'a', 'a', 'b' },

09                               { 'b', 'b', 'a', 'b', 'a' }

10                             };

11            char[][] pattern = { 

12                           { 'a', 'b' },

13                           { 'b', 'a' }

14                             };

15     

16            matrixPatternMatch(text, pattern);

17        }

18     

19        private static void matrixPatternMatch(char[][] text, char[][] pattern) { 

20            // pre-process

21            int[] patternStamp = new int[pattern[0].length];

22            int[] textStamp = new int1.length];

23     

24            caculateStamp(pattern, pattern.length, patternStamp);

25            caculateStamp(text, pattern.length, textStamp);

26     

27            int[] next = new int[patternStamp.length];

28            caculateNext(patternStamp, next);

29     

30            for (int i = 0; i < (text.length - pattern.length + 1); i++) { 

31                int col = isMatch(patternStamp, textStamp, next);

32                if (col != -1) { 

33                    System.out.println("found");

34                    System.out.println(i+", "+col);

35                }

36     

37                // move down

38                if(i < text.length - pattern.length)

39                    caculateNextStamp(text, pattern.length, textStamp, i);

40            }

41     

42        }

43     

44        private static int isMatch(int[] patternStamp, int[] textStamp, int[] next) { 

45            int i = 0, j = 0;

46            while (j < patternStamp.length && i < textStamp.length) { 

47                if (j == -1 || patternStamp[j] == textStamp[i]) { 

48                    i++;

49                    j++;

50                } else { 

51                    j = next[j];

52                }

53            }

54     

55            if (j == patternStamp.length) { 

56                return i-j;

57            } else { 

58                return -1;

59            }

60        }

61     

62        private static void caculateNext(int[] pattern, int[] next) { 

63            next[0] = -1;

64     

65            int i = 0, j = -1;

66            while(i1) { 

67                if(j==-1 || pattern[i] == pattern[j]) { 

68                    i++;

69                    j++;

70                    next[i] = j;

71                } else { 

72                    j = next[j];

73                }

74            }

75     

76        }

77     

78        private static void caculateNextStamp(char[][] text, int height,

79                int[] textStamp, int row) { 

80            int d = (int) Math.pow(26, height-1);

81            for (int i = 0; i < textStamp.length; i++) { 

82                textStamp[i] = 26 * (textStamp[i] - d * text[row][i]) + text[row + height][i];

83            }

84        }

85     

86        private static void caculateStamp(char[][] input, int height, int[] result) { 

87            for (int i = 0; i < result.length; i++) { 

88                result[i] = 0;

89                for (int j = 0; j < height; j++) { 

90                    result[i] = 26 * result[i] + input[j][i];

91                }

92            }

93        }

94     

95    }

第21-28行，进行匹配前的预处理。

第21-22行，patternStamp和textStamp分别用来存储模式矩阵以及文本矩阵的前m₁行转换成一维数字串。

第86-93行，定义函数caculateStamp，输入是一个二维字符矩阵，输出是转换成的一维数字串。对输入矩阵的每一列用霍纳法则计算出一个值，作为转换后的一维数字串的一位。

第24-25行，用函数caculateStamp计算得到转换后的一维数字串。

第27-28行，计算转换后的一维模式串的next数组，用于KMP算法进行一维串匹配。

第30-40行，进行实际的匹配。

匹配时，对文本矩阵每m₁行进行一次匹配，匹配前都转换成一维的数字串，用KMP算法（第31行）进行一维串匹配，总共要匹配n₁-m₁+1次。

第38-39行，待匹配的文本矩阵下移一行，计算转换成的新一维数字串。

第78-84行，函数caculateNextStamp，用来根据上一次的一维转换数字串计算出新的，类似于RK算法中的公式二。

时间复杂度：

预处理 – O(n₂*m₁)

计算模式矩阵的stamp O(m₁*m₂) + 计算文本矩阵前m₁行的stamp O(n₂*m₁) + 计算模式矩阵stamp的next数组 O(m₂)

匹配 – O((n₁-m₁+1)*n₂)

总共 n₁-m₁+1次

每次用KMP算法匹配 O(n₂) + 计算文本矩阵下m行的stamp O(n₂)

总的时间复杂度 – O(n₁*n₂)

[转]： http://www.slimeden.com/2010/10/algorithm/matrixpatternmatching