字符串匹配2：BM算法
BM（Boyer-Moore）算法，是一种高效的单模式串匹配算法。高效的字符串匹配算法在文本编辑器这样的软件上应用是否广泛。BM算法比著名的KMP算法更加高效。
思想
字符串匹配的过程本质上是模式串在主串上滑动匹配的过程。BF和BK的策略是每次匹配失败都向后滑动一位。
[abcdefghijklmn]
[def]
↓
[abcdefghijklmn]
[def]
↓
[abcdefghijklmn]
[def]
↓
[abcdefghijklmn]
[def]而BM算法的策略在失败后尽可能滑动更多位数。于是任务变成了如何确定滑动多少位，也有哪些情况下我们可以确定匹配不上，可以多滑动几位。当遇到不匹配的字符时，有什么固定的规律，可以将模式串往后多滑动几位呢？BM 算法，本质上其实就是在寻找这种规律。借助这种规律，在模式串与主串匹配的过程中，当模式串和主串某个字符不匹配的时候，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位。
规则
BM算法确定不匹配滑动的规则共有两条，坏字符规则（bad character rule）和好后缀规则（good suffix shift）。-BM算法通过同时应用坏字符规则和好后缀规则 ，每次取两者计算出的最大移动位数作为最终移动步长，从而最大化跳过无用比较的能力。
坏字符规则
坏字符规则相对简单，从后向前匹配，如果主串和模式串字符匹配不上，则标记为坏字符。然后从模式串中查找该坏字符。如果模式串中没有该字符，则向后滑动整个模式串长度：
[143212345436] ————> [143213345436]
[123] [123] 如果模式串中有这个字符，则滑动至对齐该坏字符：
[143213345436] ————> [143213345436]
[123] [123] 假设坏字符对应的模式串的index是 i ，而这个坏字符在模式串中的index是 j ，滑动长度如下计算方法如下：
skip = i - j需要注意的是，如果坏字符在模式串中多次出现，则对齐最后一个位置。即，如果模式串中下标为1、4同为坏字符的位置，则使用4对齐，就是也就是滑动最小的距离。
但是光靠坏字符规则有可能会向前滑动。比如，坏字符对应的模式串的index是2，而该坏字符在模式串中的最大位置是5。则需要skip是-3，向前滑动，如下面的坏字符5，而坏字符在模式串的位置是5。
[12564567576567]
[1366456]好后缀规则
从后向前匹配，坏字符之后的已匹配的子串就是好后缀。如果这个好后缀不在模式串的之前的位置，比如下面的[23]，则滑动整个模式串的长度
[223212345436] ———> [223212345436]
[123] [123] 如果这个好后缀在模式串之前的其他位置，比如下面的[23]，则用前一个位置对齐当前对齐位置
[22323345436] —————> [22323345436]
[23123] [23123] 如果这个好后缀在模式串之前的其他位置没有匹配的子串，但存在与好后缀的后缀部分匹配的前缀（即公共前后缀）。如下面的[123]存在公共前后缀[23],那么我们需要将这个前缀和好后缀的后缀进行对齐。
[22123345436] —————> [22123345436]
[23123] [23123] 需要注意的是，公共前后缀取最长的一个，比如[aabbaaa]模式串，当其好后缀的是aaa的时候，它的公共前缀可以是a也可以是aa,我们取最长的aa。因为滑动步长短，不会错过匹配。
实现
为了优化实现我们可以将坏字符规则需要用到的模式串中坏字符位置提前预处理，做成map；同样的，也可以好后缀规则中需要使用到的好后缀在模式串的的前字串位置进行预处理做成map，以及有无公共前后缀进行预处理，做成map。
package cn.lishiyuan.algorithm.strings;
import java.util.HashMap;
import java.util.Map;
/**
* Rabin-Karp 算法
*/
public class BMMatcher implements Matcher{
@Override
public boolean match(CharSequence source, CharSequence word) {
return find(source,word) != -1;
}
@Override
public int find(CharSequence source, CharSequence word) {
// codePoints或者chars
int[] sourceArray = source.chars().toArray();
int[] wordsArray = word.chars().toArray();
if (sourceArray.length < wordsArray.length){
return -1;
}
if (wordsArray.length == 0){
return -1;
}
int index = -1;
Map<Integer, Integer> badWordsTable = buildBadWordsTable(wordsArray);
Map<Integer,Integer> suffix = new HashMap<>();
Map<Integer,Boolean> prefix = new HashMap<>();
buildGoodSuffixTable(wordsArray,suffix,prefix);
int i = 0;
for (; i < sourceArray.length - wordsArray.length + 1; ){
int j = wordsArray.length - 1;
for (; j >=0 ;){
// 坏字符规则，从后向前匹配
if(wordsArray[j] != sourceArray[i+j]){
break;
}
j--;
}
// j 是坏字符位置
if (j == -1){
// 找到了
index = i;
break; }
// 从坏字符表中查找
int badWord = sourceArray[i+j];
Integer badWordIndex = badWordsTable.getOrDefault(badWord, -1);
// 坏字符规则移动的步长
int x = j - badWordIndex;
// 好后缀规则移动的步长
int y = 0;
// 好后缀最少一个字符
if(j < (wordsArray.length-1)){
// 处理好后缀的情况
// 好后缀的长度
int len = wordsArray.length - 1 - j;
Integer suffixIndex = suffix.getOrDefault(len, -1);
if(suffixIndex != -1){
// 如果存在前一个好后缀，则需要对齐
/**
* 123223424 * 323423 * 此时23好后缀的前一个位置是1，此时坏字符位置是3，需要滑动3个位置才能对齐
*/
y = (j - suffixIndex + 1);
}else {
// 前缀对齐
// j是坏字符位置，j + 1就是好后缀长度，此时好后缀必然不存在，所以r从j+2开始
int r = j + 2;
for (; r < wordsArray.length; r++) {
// 获取好后缀的后缀是否有公共前后缀，串长度= length - index
if (prefix.getOrDefault(wordsArray.length - r,false)) {
y= r;
break; }
}
}
}
i += Math.max(x,y);
}
return index;
}
private Map<Integer,Integer> buildBadWordsTable(int[] wordsArray){
Map<Integer, Integer> badwords = new HashMap<>();
for (int i = 0; i < wordsArray.length; i++) {
// 如果有相同的字符，使用后一个index替换掉
badwords.put(wordsArray[i], i);
}
return badwords;
}
private void buildGoodSuffixTable(int[] wordsArray,Map<Integer,Integer> suffix,Map<Integer,Boolean> prefix){
// 构建
for (int i = 0; i < wordsArray.length - 1; i++) {
int j = i;
int len = 0;
// i->0 与 末尾 -> j 进行逆序的对比
// 每次都会从最后一个字符开始匹配，这使得始终存靠近末尾的子串
// 相当于每次从j到0寻找匹配模式串末尾到len长度的子串
/**
* [1][2][3][4][5][5] * ←j↑ ←(↑ wordsArray.length - 1 -len ) */ while (j >= 0 && wordsArray[j] == wordsArray[wordsArray.length - 1 -len]){
suffix.put(len,j);
j--;
len++;
}
// 如果匹配首位则说明可以对齐公共前后缀
if(j == -1){
prefix.put(len,true);
}
}
}
}重点是坏字符表、好后缀和公共前后缀的构建和应用。选择两个规则中滑动步长大的那个进行滑动。
本质上，BM算法是充分利用模式串特征，向后滑动尽可能大的长度，以加速匹配。
评论已关闭