Boyer-Moore算法的实现

stormzhang 发布于2019-08-14 12:08 / 2523人阅读

摘要：算法用于搜索匹配字符串，如中的查找功能，是一个十分巧妙高效的算法。如果好后缀有多个，则除了最长的那个好后缀，其他好后缀的上一次出现位置必须在头部。

Boyer-Moore算法用于搜索匹配字符串，如Word中的查找功能，是一个十分巧妙高效的算法。下面是Moore教授自己给出的例子:
http://www.cs.utexas.edu/~moore/best-ideas/string-searching/index.html
根据上面的例子来说一下算法思想：
假定被匹配的字符串为A”This is a simple Example" 搜索的字符串为B“Example”
与暴力匹配不同的是，这个算法从搜索字符串的结尾开始匹配，将A和B的头对齐。如果结尾不同，那么前面的字符串也都不需要比较了。
步骤：
this is a simple example
example
显然“s"和”e“不一样，s就是一个坏字符串。然后把B字符串后移，后移公式为
后移位数 = 坏字符串的位置 - 上一次在字符串B中出现的位置。
如s，后移位数 = 坏字符串位置（6，相对于example，从0开始数） - 上次出现的位置（没有出现，为-1） = 7
所以把B往后移动7位，直接到了s的后一位。
如此，当我们进行到下面这一步：
this is a simple example
example
B中”mple"和A中相匹配，我们把“mple”称为好后缀（good suffix),同时“ple","le","e"都是好后缀。此时比较"I"和‘a’不同，需要把字符串往后移，此时因为存在好后缀，移动规则如下：
后移位数 = 好后缀的位置 - 上次出现好后缀的位置

"好后缀"的位置以最后一个字符为准。假定"ABCDEF"的"EF"是好后缀，则它的位置以"F"为准，即5（从0开始计算）。

　　如果"好后缀"在搜索词中只出现一次，则它的上一次出现位置为 -1。比如，"EF"在"ABCDEF"之中只出现一次，则它的上一次出现位置为-1（即未出现）。

　　如果"好后缀"有多个，则除了最长的那个"好后缀"，其他"好后缀"的上一次出现位置必须在头部。比如，假定"BABCDAB"的"好后缀"是"DAB"、"AB"、"B"，请问这时"好后缀"的上一次出现位置是什么？回答是，此时采用的好后缀是"B"，它的上一次出现位置是头部，即第0位。这个规则也可以这样表达：如果最长的那个"好后缀"只出现一次，则可以把搜索词改写成如下形式进行位置计算"(DA)BABCDAB"，即虚拟加入最前面的"DA"。
如上例：mple 好后缀位置为6（e的位置），上次出现位置为0（e在开头出现了）
那么往后移动6位。

下面给出实现了规则一的代码，完整的BM算法稍后补充：

    package BM字符串匹配算法;

public class BM {
    private int[] right;//用来记录A字符串中的字符在字符串B中所在的位置
    private String pat;//目标字符串，也就是字符串B
    BM(String pat){
        this.pat = pat;
        int M = pat.length();
        int R = 256;//ASCII 码 256种可能的字符
        right = new int[R];
        for(int c = 0;c < R;c++)
            right[c] = -1; //初始化，全都为-1
        for(int j = 0;j < M;j++)
            right[pat.charAt(j)] = j;//在pat中出现的最右的位置

    }

    public int search(String txt){
        int N = txt.length();
        int M = pat.length();
        int skip;
        for(int i = 0;i <= N - M;i += skip){
            //目标字符串B和被匹配字符串在i位置是否相同
            skip = 0;
            for(int j = M-1;j >=0;j--){
                if(pat.charAt(j) != txt.charAt(i+j)){
                    skip = j -right[txt.charAt(i+j)]; //规则一skip等于坏字符串的位置-上一次出现的位置
                    if(skip < 1) skip = 1;
                    break;
                }
            }
            if(skip == 0) return i;//找到匹配
        }
        return N;//未找到匹配
    }
    public static void main(String args[]){
        String pat = "example";
        String txt = "this is a example";
        BM bm = new BM(pat);
        System.out.print(bm.search(txt));
    }
}

使用BM算法在一般情况下，对于长度为N的文本和长度为M的模式字符串需要1 - N/M次比较。

服务器托管专线服务最佳置换算法的实现最容易实现的替换算法自主设计编程实现遥感图像处理的各种算法算法实现

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64310.html

Majority Vote Alogrithm（最大投票算法）及其扩展

摘要：，这是最基础的最大投票算法。例如，和这两个数组最后得到的分别为和，但是这并不影响答案的正确性。接下来，我们可以对这个算法做一些简单的扩展，我们当前定义的的数量大于的元素。为当前出现的次数。这意味着当前这个数字就是这两个等待的第三个数字。 Boyer-Moore：A Linear Time Majority Vote Alogrithm，这是最基础的最大投票算法。原文中提到：decid...

niceforbear 2019-08-14 15:25 评论0 收藏0
用 PHP 的方式实现的各类算法合集

摘要：数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据的逻辑结构数据元素之间的相互关系称为逻辑结构。项目地址 https://github.com/m9rco/algo... 每周最少一更，求出题，求虐待 At least once a week, ask for problems and abuse 简...

Karrdy 2019-06-28 13:32 评论0 收藏0
用 PHP 的方式实现的各类算法合集

摘要：数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据的逻辑结构数据元素之间的相互关系称为逻辑结构。项目地址 https://github.com/m9rco/algo... 每周最少一更，求出题，求虐待 At least once a week, ask for problems and abuse 简...

pakolagij 2019-07-25 15:02 评论0 收藏0