2.1 纯字符串匹配_深入浅出 Hyperscan：高性能正则表达式算法原理与设计-QQ阅读女生中文短篇网

上QQ阅读APP看书，第一时间看更新

2.1　纯字符串匹配

2.1.1　单字符串匹配KMP算法

字符串匹配问题的基本情境是这样的：给定一个搜索串（输入语料）和一个模式串（字符串规则），如何查找在中的位置？首先需要将和对齐，然后从头开始比较二者在每一个对齐位置上的字符是否相同，只要相同就各自查看下一位。如果从模式串的开始位置到结尾位置的字符序列都和搜索串中相同，就说明成功找到了在中的匹配。但如果在某个位置上，模式串的字符和搜索串的字符不相同呢？下一步该怎么办？解决思路有多种。如果采用暴力匹配的思路，假设某个时刻发生了这种两边字符不相同的情况，或者称为“失配”，并且失配的字符分别位于搜索串的第位、模式串的第位，即，那么暴力匹配的下一步是：令，且。这相当于每次失配时，搜索串需要回溯到上一轮开始位置的下一位，模式串则需要从头再来。不同的算法在失配发生时，采取的后续跳转方法各有不同，暴力匹配只是最保守的情况。

KMP（Knuth-Morris-Pratt）算法是一种用于单字符串匹配的传统算法，其时间复杂度为，其中为搜索串长度。其匹配过程中依次将搜索串每个位置的字符与模式串特定位置的字符做比较。工作特点为搜索串的位置不做回溯。当前位置匹配的情况下搜索串位置和模式串位置同步递增1，而失配的情况下搜索串停留原位置与模式串当前位置的失配跳转位置再做比较。其运行期算法很简洁，关键在于预处理，即根据模式串自身的特点计算出失配函数，即模式串每个位置的失配跳转位置。

KMP算法运行的伪代码如下：

1   #s  : string for scan
2   #p  : string pattern
3   #miss  : mismatch function
4  
5   function kmp_runtime(s, p, miss)
6      i := 0;
7      j := 0;
8      while i < strlen(s) do
9         if (j = -1) || (s[i] = p[j]) then
10           i := i + 1;
11           j := j + 1;
12        else
13           j := miss[j];
14        end if
15        if j = strlen(p) then
16           report match @ (i – 1);
17           j := miss[j];
18        end if
19     end while
20  end function

其中预处理计算模式串的失配函数是算法的关键，在发生失配时不能简单地将搜索串失配位置的字符与模式串开头位置的字符做下一步比较，因为在发生失配的前一个位置上必有模式串的某个子串产生了匹配，所以该子串的所有严格后缀（除去该子串本身的后缀）也产生了匹配。若该子串的某严格后缀同样为模式串前缀，那么该前缀部分也是产生了匹配的。若将模式串失配位置的失配函数值直接置0，就会跳过产生匹配的前缀部分，从而可能丢失潜在的匹配。

图2.1展示了一个丢失匹配的例子。假设有模式串abcabe，对图中的搜索串进行匹配，在位置5发生失配，但此时位置3、4上有子串abcab的后缀ab发生匹配，且ab又恰是abcab的前缀，若简单地将失配函数值置0，即模式串向后移动6个位置，则会漏掉从位置3到位置8的真实匹配。

图2.1　失配函数值置0的漏报风险

为了不漏掉这类潜在的匹配，模式串每个位置的失配函数值应当设为该位置之前的子串的严格后缀，且为模式串最长前缀的后一个位置的值。

编译期模式串失配函数在各个位置的值可通过如下伪代码来计算：

1   #p    : string pattern
2   #miss : mismatch function
3  
4   function kmp_compile(p, miss)
5      miss[0] := -1;
6      i := 0;
7      j := -1;
8      while i < strlen(p) do
9         if (j = -1) || (p[i] = p[j]) then
10           i := i + 1;
11           j := j + 1;
12           miss[i] := j;
13        else
14           j := miss[j];
15        end if
16     end while
17  end function

例如，对给定模式串abcabc，其失配函数值如图2.2所示。