Algorithms

Pattern matching相关算法小结

Pattern matching的算法有很多，这里做一个简单的总结。

Pattern matching

Pattern matching的算法有很多，这里做一个简单的总结。

问题：给定一个字符串txt[0...n-1]和另一个字符串pat[0...m-1]，假设n > m，实现一个函数search(char pat[], char txt[])，完成在txt中找到所有pat出现的位置。

例子：

  • Input:
1
2

txt[] = "THIS IS A TEST TEXT"
pat[] = "TEST"

Output:

1

Pattern found at index 10
  • Input:
1
2

txt[] = "AABAACAADAABAAABAA"
pat[] = "AABA"

Output:

1
2
3

Pattern found at index 0
Pattern found at index 9
Pattern found at index 13

Naive Pattern Searching

也叫Bruce Force。

方法很简单，对于txt中的每个index i，检查pat的每个字符是否匹配。如果有匹配不上的字符，或者匹配成功，都move到下一个index。

最坏时间复杂度，$O(mn)$。

References

A Better Naive Pattern Searching

这个方法需要有一个前提条件：pat里所有字符都不相同。

在这个前提下，如果在匹配了j个字符之后出现了mismatch，那么pat就不是后移一个位置，而是后移j个位置。当然如果是首字符就不匹配，那么仍然是后移一个位置。

References

KMP Algorithm

Naive Pattern Searching在这样的情况下，效率是很低的：

1
2

txt[] = "AAAAAAAAAAAAAAAAAB"
pat[] = "AAAAB"

因为pat每次在比较到不同的字符B的时候，仅仅向后移动一位，搜索位置又要退回，重新比较已经比较过的字符。

同时这也是Naive Pattern Searching的改进方法无法处理的，因为里面出现了重复的字符。如果再回去看Naive Pattern Searching的改进方法，其实本质上就是为了避免搜索位置的退回。

KMP可以利用已经比较过的字符这一信息来避免搜索位置退回。至于怎么利用，就是部分匹配表。

部分匹配表是KMP的关键，生成的方式是对pat的每个前缀，计算该前缀的前缀和后缀的最长的共有元素的长度。例如：

1
2

pat                 A B C D A B D
partial match value 0 0 0 0 1 2 0

有了部分匹配表，在发现不同的字符的时候，就不直接把pat后移一位，而是根据下面的公式，

$$ 移动位数 = 已匹配的字符数 - 对应的部分匹配值 $$

这里对应的部分匹配值指的是，在pat中，最后已匹配字符对应的部分匹配值。

如果是首字符就不匹配，那么仍然是后移一个位置。

“部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，"ABCDAB"之中有两个"AB"，那么它的"部分匹配值"就是2（“AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（$字符串长度-部分匹配值$），就可以来到第二个"AB"的位置。

最坏时间复杂度，$O(n)$。

看完KMP，可以发现Naive Pattern Searching的改进方法实际上是KMP的特例，由于pat中所有字符都不相同，因此部分匹配表中所有的对应的部分匹配值都是0，

$$ 移动位数 = 已匹配的字符数 $$

References

Rabin-Karp Algorithm

Bruce Force在txt上每次把pat后移一位，每次移动之后，检查pat的每个字符是否匹配。Rabin-Karp也是类似的，每次把pat后移一位，不同的是Rabin-Karp比较的是pat的hash值和当前对应的txt子串的hash值。如果hash值相等，然后再去逐个检查子串的字符。

最直接的方法莫过于计算h(pat)和txt中所有子串的hash，然后一一比较。但光是计算txt中所有子串的hash就需要O(mn)的时间，这样一来，相比起Naive Pattern Searching，这个方法就毫无优势了。

如何计算hash值是Rabin-Karp的关键，最好是能够利用当前txt子串的hash值，计算后移一位以后的，以减少计算的开销。Rabin-Karp使用的hash叫做Rolling hash，基本实现是刚刚的方法实际上重复计算了很多重叠的部分，而Rolling hash就要利用当前子串的hash值，来计算后移一个位置之后子串的hash值。

Intro to Algorithms的Lecture Note举了一个很形象的例子来说明Rolling hash。

在最坏情况下，每次移动后hash值都相等（因为子串相同或hash冲突），因此移动后都要逐个检查子串的字符。

最坏时间复杂度，$O(mn)$。

References

Finite Automata

基于有限状态机实现pattern searching，就是用pattern来构建一个状态表，构建完成以后就可以根据txt的每个字符，来在有限状态机的各个状态之间转移，如果到达终态，那就是匹配到了。

这个算法的关键就是基于pattern构建状态表。

References

http://www.geeksforgeeks.org/searching-for-patterns-set-5-finite-automata/

comments powered by Disqus