在文本处理中，关键字匹配是一个十分常用且重要的功能。关键字称为模式串，在文本T中寻找模式串P出现的所有出现的位置，解决这种问题的算法叫做字符串匹配算法。字符串匹配算法可以说是计算机科学中最古老、研究最广泛的问题之一，并且字符串匹配的应用也随处可见，特别是信息检索领域和计算生物学领域。
模式匹配算法有很多很多，其中比较著名的算法有：KMP（Knuth-Morris-Pratt）算法，BM（Boyer-Moore）算法，Sunday 算法和Horspool算法。接下来将简单介绍模式匹配中的几种常见的算法。
1.朴素匹配算法
朴素匹配算法是一种暴力匹配方法，从文本的开头通过依次比较的方式向后对模式串进行匹配。朴素匹配算法是一种比较容易想到且实现比较容易的方法，假设文本T长度为m，模式串P长度为n。算法从文本第1位从左向右开始与模式串P进行匹配，无论是否匹配成功，模式串都后移1位开始继续进行重新匹配，总共进行m-n+1次匹配。算法极其简单，因此效率极其有限，时间复杂度为O(m*n)，故不常被用，这里不做详细介绍。
2.KMP算法
| 位置 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 模式串 | 圈 | 圈 | 大 | 师 |
| 部分匹配值 | 0 | 1 | 0 | 0 |
KMP算法是由三名科学家（Knuth，Morris，Pratt）联合提出的模式匹配方法。KMP是一种相对高效的模式匹配算法，它的高性能的原因在于它可以通过利用字符串匹配过程中的失败信息来减少模式匹配的次数，进而提升匹配性能。
KMP算法借助了一个辅助的结构——部分匹配表，部分匹配表是针对模式串产生的一个辅助信息表，通过该表，可以在匹配失败时，降低无用的匹配次数。部分匹配表的长度与模式串长度相同，部分匹配子是当前字符对应的“前缀”和“后缀”的最长公共元素的个数。
假设现在有个模式串“圈圈大师”，我们可以通过如下的过程得到部分匹配表：
（1）对于第一个“圈”，它的前缀和后缀都为空，因此共有元素的数目为0，所以第一个“圈”的部分匹配值为0；
（2）对于“圈圈”，它的前缀为“圈”，后缀为“圈”，共有元素的数目为1，所以第二个“圈”的部分匹配值为1；
（3）对于“圈圈大”，它的前缀为“圈”、“圈圈”，后缀为“大”、“圈大”，共有元素的数目为0，因此第三个字的部分匹配值为0；
（4）对于“圈圈大师”，它的前缀为“圈”、“圈圈”、“圈圈大”，后缀为“师”、“大师”，“圈大师”。共有元素的数目为0，因此第四个字的部分匹配值为0；
以上，我们可以得到如下的部分匹配表。
| 位置 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 模式串 | 圈 | 圈 | 大 | 师 |
| 部分匹配值 | 0 | 1 | 0 | 0 |
部分匹配表是KMP算法进行字符串查找的重要参考依据，因此有了部分匹配表之后，我们可以对文本“画圈圈的圈圈大师傅”进行模式串“圈圈大师”的匹配。匹配方式为：
每次开始从左向右匹配，若前k位匹配成功，则 后移位数s = 当前已匹配的字符数k - 最后一个匹配字的部分匹配值。
匹配过程如下：
step1：
画圈圈大的圈圈大师
圈圈大师
step2：
画圈圈大的圈圈大师
〇圈圈大师
step3：
画圈圈大的圈圈大师
〇〇〇〇圈圈大师
step4：
画圈圈大的圈圈大师
〇〇〇〇〇圈圈大师
KMP算法分为两个步骤，先通过P计算出部分匹配表，时间复杂度为O(n)；再通过此表进行匹配位移，时间复杂度为O(m)，故理论上的总时间复杂度为O(m+n)，达到线性效率。理论效率高，但实际上却未特别突出。
KMP代码实现如下(JAVA)：
3.Boyer-Moore算法
Boyer-Moore算法简称为BM算法，是一种与KMP算法同等重要的模式匹配算法。BM算法相对于KMP算法效率更高，且更容易理解和实现。
与KMP有两个不同点：
①每次匹配时，匹配方向不同，BM算法每次从右向左匹配，此类算法隶属于基于后缀搜索的方法。
②匹配后向后偏移的位数由两种计算方式得到：坏字符偏移和好后缀偏移。
step1:
HERE IS A SIMPLE EXAMPLE
EXAMPLE
首先，原字符串和子串左端对齐，但是从尾部开始比较，就是首先比较“S”和“E”，这是一个十分巧妙的做法，如果字符串不匹配的话，只需要这一次比较就可以确定。
在BM算法中，当每次发现当前字符不匹配的时候，我们就需要寻找一下子串中是否有这个字符；比如当前“S”和“E”不匹配，那我们需要寻找一下子串当中是否存在“S”。发现子串当中并不存在，那我们将子串整体向后移动到原字符串中“S”的下一个位置：
step2:
HERE IS A SIMPLE EXAMPLE
EXAMPLE
我们接着从尾部开始比较，发现“P”和“E”不匹配，那我们查找一下子串当中是否存在“P”，发现存在，那我们就把子串移动到两个“P”对齐的位置：
step3:
HERE IS A SIMPLE EXAMPLE
EXAMPLE
依然从尾部开始比较，“E”匹配，“L”匹配，“P”匹配，“M”匹配，“I”和“A”不匹配！那我们就接着寻找一下子串当前是否出现了原字符串中的字符，我们发现子串中第一个“E”和原字符串中的字符可以对应，那直接将子串移动到两个“E”对应的位置：
step4:
HERE IS A SIMPLE EXAMPLE
EXAMPLE
从尾部比较，发现“P”和“E”不匹配，那么检查一下子串当中是否出现了“P”，发现存在，那么移动子串到两个“P”对应：
step5:
HERE IS A SIMPLE EXAMPLE
EXAMPLE
从尾部开始，逐个匹配，发现全部能匹配上，匹配成功！
目前很多的文本编辑器中的查找方法都是基于BM算法实现的，相对于KMP算法，其实用性更高，且效率通常为KMP算法的3~5倍。
BM算法代码实现如下(JAVA)：
4.Sunday算法
step1:
HERE IS A SIMPLE EXAMPLE
EXAMPLE
首先原字符串和子串左端对齐，发现“T”与“E”不匹配之后，检测原字符串中下一个字符（在这个例子中是“IS”后面的那个空格）是否在子串中出现，如果出现移动子串将两者对齐，如果没有出现则直接将子串移动到下一个位置。这里空格没有在子串中出现，移动子串到空格的下一个位置“A”：
step2:
HERE IS A SIMPLE EXAMPLE
EXAMPLE
发现“A”与“E”不匹配，但是原字符串中下一个字符“E”在子串中出现了，第一个字符和最后一个字符都有出现，那么首先移动子串靠后的字符与原字符串对齐：
step3:
HERE IS A SIMPLE EXAMPLE
EXAMPLE
发现空格和“E”不匹配，原字符串中下一个字符“空格”也没有在子串中出现，所以直接移动子串到空格的下一个字符“E”：
step4:
HERE IS A SIMPLE EXAMPLE
EXAMPLE
从头开始逐个匹配，匹配成功！
在Sunday算法的比较过程中最核心的点在于：如果当前匹配失败，则根据模式串与文本的对应部分的后面一个字符串作为跳转的依据，如果该字符不在模式串中，则直接略过，模式串直接跳到下一位进行匹配；如果该字符在模式串中，怎将模式串对齐到最后一个与当前字符相同的位置，然后再从头进行比较。
Sunday算法代码实现如下(JAVA)：
public static List<Integer> Sunday(String txt, String part){
List<Integer> locs = new ArrayList<Integer>();
final int tlen = txt.length();
final int plen = part.length();
for(int start = 0, newS = 0; start + plen <= tlen; ){
if(isPattern(start, txt, part)){
locs.add(start);
start += plen;
}else{
newS = start + plen;
if(newS >= tlen)
break;
int lIndex = part.lastIndexOf(txt.charAt(newS));
if(lIndex == -1){
start = newS ++;
}else{
start += plen - lIndex;
}
}
}
return locs;
}
private static boolean isPattern(int start, String txt, String part){
boolean isPattern = true;
//异常数据排除
if(null == txt || null == part || start >= txt.length() || start + part.length() > txt.length()){
isPattern = false;
}
//判断字符串是否匹配
for(int i = 0; isPattern && i < part.length(); i++){
if(txt.charAt(i + start) != part.charAt(i)){
isPattern = false;
break;
}
}
return isPattern;
}
网友评论