江苏龙网

  1. 主页 > 生活百科 > >

那些经典算法：字符串匹配算法BM算法( 二 )

BM算法


那些经典算法：字符串匹配算法BM算法

文章插图
 
。
总结下，好后缀有两种移动方法： 1）如果好后缀子串{u}在模式串中存在{u*}完全匹配，则移动模式串，将最近的u*和主串对齐 。2）如果好后缀子串{u}在模式串中不存在，如果{u}的后缀子串有和模式串中的前缀子串匹配的{v‘} 则移动模式串和主串中的相应位置重合 。3）如果后缀子串{u}在模式串中不存在，且{u}的后缀子串在模式串中前缀子串没有匹配的，则将模式串移动到匹配的好后缀子串后面即可 。
二、算法实现通过原理我们知道坏字符规则和好后缀规则都涉及到查找问题，如果查找性能不是很好，BM算法很难有好的性能，所以在工程实践上，BM算法还是有不少技巧的 。
我们在计算坏字符规则移动的位数的时候，需要通过si-xi来计算，si一般可以直接得到，xi怎么计算，xi为坏字符在模式串中的位置，如果一个个比对，性能肯定跟不上，假设字符集不是很大，我们可以用一个256数组，来记录每个字符在模式串中的位置，数组下标可以直接对应字符的ASCII码值，数组的值为字符在模式串中的位置：
那些经典算法：字符串匹配算法BM算法

文章插图
 
说明下： 1）bc数组就是我们通过遍历模式串得到的数组 。2）模式串里面有2个a，最终bc[97] = 3 标识坏字符a在模式串中的位置应该为3，这是因为坏字符在模式串中如果有多个匹配，只能用后面一个，这样步字小一点 。97即为a的ascii值 。
private static final int SIZE = 256; // 全局变量或成员变量private void generateBC(char[] b, int m, int[] bc) {for (int i = 0; i < SIZE; ++i) {bc[i] = -1; // 初始化 bc}for (int i = 0; i < m; ++i) {int ascii = (int)b[i]; // 计算 b[i] 的 ASCII 值bc[ascii] = i;}}代码比较简单，先不考虑好字符规则，只用坏字符规则，这里面存在着移动位置为负数的问题，写下BM算法的代码：
public int bm(char[] a, int n, char[] b, int m) {int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置generateBC(b, m, bc); // 构建坏字符哈希表int i = 0; // i 表示主串与模式串对齐的第一个字符while (i <= n - m) {int j;for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是 j}if (j < 0) {return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置}// 这里等同于将模式串往后滑动 j-bc[(int)a[i+j]] 位i = i + (j - bc[(int)a[i+j]]);}return -1;}好后缀规则的要求：
  • 在模式串中查找跟好后缀匹配的另一个子串，如果查找到按照规则走，查找不到 。
  • 在好后缀的子串中，查找最长的，能够跟模式串前缀子串匹配的后缀子串 。
字符串的后缀子串，因为字符串结尾字符是固定的，只要存储长度就可以推出后缀子串，如下图：
那些经典算法：字符串匹配算法BM算法

文章插图
 
后缀子串b 值为1，标识后缀子串，长度为1，我们就知道从后向前一个字节，依次类推 。
现在我们引入关键的变量数组suffix数组，下标k标志后缀子串的长度，值为在模式串中除了好后缀子串在模式串中的匹配之前的匹配的后缀子串的位置：
那些经典算法：字符串匹配算法BM算法

文章插图
 
同样为了避免模式串滑动过头，如果模式串中有多个子串跟后缀子串{u}匹配，那么suffix数组存的是模式串中最靠后的子串起始位置 。
这样还不够，查找跟好后缀匹配的另一个子串，还要在好后缀的后缀子串中，查找最长的能够跟模式串的前缀子串匹配的后缀子串 。所以我们需要另一个boolean的prefix数组，来记录模式串（也是好后缀的）的后缀子串是否能够匹配模式串的前缀子串 。
那些经典算法：字符串匹配算法BM算法

文章插图
 
说明：
  • 图中后缀子串b，和模式字符串的前缀子串不匹配，因为匹配的话第一字符必须是c 。
  • 图中只有cab这个后缀子串才和模式串的前缀子串相互匹配 。
  • 其他的类似 。suffix 和prefix数组的计算过程如下：
// b 表示模式串，m 表示长度，suffix，prefix 数组事先申请好了private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {for (int i = 0; i < m; ++i) { // 初始化suffix[i] = -1;prefix[i] = false;}for (int i = 0; i < m - 1; ++i) { // b[0, i]int j = i;int k = 0; // 公共后缀子串长度while (j >= 0 && b[j] == b[m-1-k]) { // 与 b[0, m-1] 求公共后缀子串--j;++k;suffix[k] = j+1; //j+1 表示公共后缀子串在 b[0, i] 中的起始下标}iif (j == -1) prefix[k] = true; // 如果公共后缀子串也是模式串的前缀子串}}


推荐阅读


上一篇：Mac访达的搜索功能如何使用？

下一篇：服务器搭建网站时，是选http还是https？