bm算法 订阅
在计算机科学里,Boyer-Moore字符串搜索算法是一种非常高效的字符串搜索算法。它由Bob Boyer和J Strother Moore设计于1977年。此算法仅对搜索目标字符串(关键字)进行预处理,而非被搜索的字符串。虽然Boyer-Moore算法的执行时间同样线性依赖于被搜索字符串的大小,但是通常仅为其它算法的一小部分:它不需要对被搜索的字符串中的字符进行逐一比较,而会跳过其中某些部分。通常搜索关键字越长,算法速度越快。它的效率来自于这样的事实:对于每一次失败的匹配尝试,算法都能够使用这些信息来排除尽可能多的无法匹配的位置。 展开全文
在计算机科学里,Boyer-Moore字符串搜索算法是一种非常高效的字符串搜索算法。它由Bob Boyer和J Strother Moore设计于1977年。此算法仅对搜索目标字符串(关键字)进行预处理,而非被搜索的字符串。虽然Boyer-Moore算法的执行时间同样线性依赖于被搜索字符串的大小,但是通常仅为其它算法的一小部分:它不需要对被搜索的字符串中的字符进行逐一比较,而会跳过其中某些部分。通常搜索关键字越长,算法速度越快。它的效率来自于这样的事实:对于每一次失败的匹配尝试,算法都能够使用这些信息来排除尽可能多的无法匹配的位置。
信息
算法类型
字符串搜索算法
发明人
Bob Boyer和J Strother Moore
发明时间
1977年
中文名
BM字符串搜索算法
学    科
计算机科学
外文名
BM String Searching Algorithm
BM算法定义
收起全文
精华内容
下载资源
问答
  • BM算法

    万次阅读 多人点赞 2017-10-20 13:58:08
    BM算法BM算法就是这样的一个算法。首先它和KMP算法一样都是从主串的最左端开始,然后不断右移的:  不同之处在于,BM算法每次判断匹配时是从右往左比较的。  下面给出的是一个简单的后缀比较的BF算法,而它和BM...

    BM算法

     BM算法就是这样的一个算法。首先它和KMP算法一样都是从主串的最左端开始,然后不断右移的:
    BM

     不同之处在于,BM算法每次判断匹配时是从右往左比较的。
    BM

     下面给出的是一个简单的后缀比较的BF算法,而它和BM算法的区别就在于++patAt的不同:

    int postfixBfMatch(const string & text, const string & pat)
    {
    
        //patAt指向了当前pat和text对齐的位置
        int patAt = 0;
        int cmp;
        const size_t PATLAST = pat.length() - 1;
        while (patAt + pat.length() <= text.length())
        {
            cmp = PATLAST;
            //如果匹配成功,cmp就会来到-1的位置上
            for (cmp = PATLAST; cmp >= 0 && pat[cmp] == text[patAt+cmp]; --cmp);
    
            if (cmp == -1)
                break;
            else
                ++patAt;
        }
    
        return patAt;
    }

     我们对BM算法的实现就是从对以上程序的优化开始的。

    坏字符

     我们现在将匹配过程中,主串失配位置的字符称之为“坏字符”。根据这个坏字符,我们可以“总结出一些教训”,进而改进以上的算法。
    imag

    基本思路

     显然当我们遇到了坏字符的时候,就需要移动模式串。问题是要移动多少呢?
     考虑两种情况:
    1. 坏字符不存在于模式串的集合中
    这是我们非常乐于看到的情况。试想如果出现这种情形,那么就意味着模式串不可能与该字符的位置有任何重合。在这种情况下,我们只需将整个模式串都移动到该坏字符之后的位置就行了
    imag

    1. 坏字符存在于模式串的集合中
      这种情况略有些复杂。一般我们的做法是找到模式串里从右往左第一个和这个坏字符匹配的字符,然后移动模式串让该字符和坏字符对齐。
      不过这样做有一个问题,因为显然这样可能造成模式串倒退移动。但是我们仔细分析,显然如果遇到了要倒退的情况,那么肯定不可能是我们要找的匹配位置。因为模式串是从左向右移动匹配的,所以在任意比较位置之前的位置都不可能是目标位置
      为了解决这个问题,我们也可以做一个小修改,如果检测到要位移量会小于零,那我们就右移一位(后面会看到,还有更好的办法)。

    imag

    bc表

     那么要怎么移动呢?又如何确定遇到坏字符的时候,要向右移动多少呢?
     首先来看第一个问题。首先明确一点,基于我们之前给出的程序框架中两个指针分别为patAtcmp,我们最好不要像KMP算法中那样直接改变cmp的值。更好的办法是直接给出位移量,然后移动patAt:

    patAt += motion

    motion是多少呢?显然它应该是cmp到模式串中和坏字符相同的最右端的字符位置的距离。即:

    motion = cmp - location(badchar)

     但还有一个问题,如果坏字符不存在,lacation有该是什么呢?这里我们就想到了我们在KMP算法中使用的通配符了,在这里我们依然这么做。所以对于任意的nonExist坏字符不属于模式串的集合,则有:

    location(nonExist) = -1;

     仔细计算一下,我们就会发现,这种情况下,刚好能够让整个模式串调到坏字符的下一位。
     那么这样一来,我们就只剩下一个最关键的问题了:location要怎么求得?难道要写一个以char为参数返回int的函数?
     我们仔细观察一下,就会发现location的值只和模式串本身有关,这让我们不禁想到了可以像KMP一样预先构建一个表——在这里我们称之为bc表。但是问题没那么简单,因为在这里,输入的badchar的种类范围极多,不可能构建出一个像next表那样的简单的数组表。所以这里我们就可以看到该算法的一个关键思路:那就是构造一个以字符本事为键值的hash表,凡是存在与模式串中的字符对应的位置的值都是该字符最后一次出现的位置;其余不想管字符,如我们之前所言,通通置为-1。具体算法如下:

    int * getBc(const string & pattern)
    {
        //256是字符表的规模大小(ACSII)
        int *bc = new int[256];
        int len = pattern.length();
    
        for (int i = 0; i < 256; ++i)
            bc[i] = -1;
    
        for (int i = 0; i < len; ++i)
        {
            bc[pattern[i]] = i; 
        }
        return bc;
    }

     由于字符本质上还是int类型,我们可以很方便地用数组来实现hash表。这里我们将hash表的尺寸置为ASCII码表的规模——256,然后同一赋值为-1。
     接下来,我们遍历模式串,每个字符本身就是它的哈希码,它的索引则是保存的值。注意这里很有技巧性的一点是我们是从左往右遍历的。这样的好处就在于即使模式串中存在相同的字符,后来的字符也会用自己的索引值覆盖掉之前赋予的值

    bc表的值代表了给定的字符在模式串上最后一次出现的位置。
    对于不存在的字符,假定模式串前面还有一个通配符,任何字符都可以在哪里出现。

     做完了这些工作,我们就可以利用这张bc表来优化算法了:

    int bmMatch(const string & text, const string & pat)
    {
        int *bc = getBc(pat);
        //patAt指向了当前pat和text对齐的位置
        int patAt = 0;
        //cmp指向了当前比较的位置
        int cmp;
        const size_t PATLASTID = pat.length() - 1;
        const size_t patLen = pat.length();
        const size_t textLen = text.length();
        while (patAt + patLen <= textLen)
        {
            //如果匹配成功,cmp就会来到-1的位置上
            //patAt + cmp 指向了text上当前比较的字符
            for (cmp = PATLASTID; cmp >= 0 && pat[cmp] == text[patAt + cmp]; --cmp);
    
            if (cmp == -1)
                break;
            else
            {
                int span = cmp - bc[text[patAt + cmp]];
                patAt += (span > 0)? span : 1;
            }
        }
        delete[] bc;
        return (patAt + patLen <= textLen)? patAt : -1;
    }

    坏字符算法评估

    • 最佳情况:$O(m/n)$
      考虑下面这种情况,显然每次比对,模式串都会直接跳过4个位置。在类似于这种情况的情形下,BM算法格外优秀。
      更一般的说,如果匹配的时候失配的概率越高,BM的表现越优秀。所以,BM算法更适用于在字符规模较大的情形下(ASCII, Unicode)
    xxx1xxx1xxx1···xxx1
    0000
    • 最坏情况:$O(mn)$
      很遗憾的是仅靠坏字符算法,也可能会变得效率极为低下。比如这种情况:
    0000000····0000
    1000

     仔细观察,你就会发现在以上的情况下,算法的执行流程完全等同于BF算法。效率极为低下的原因在于该算法完全无视了之前存在部分匹配的事实。所以仅有坏字符策略是不够的,再次基础上我们还要在加上其他的一些策略。

    好后缀

    基本思路

     在有了坏字符的基础上我们还要加上所谓的“好后缀”策略。所谓好后缀就是从后往前匹配部分的后缀。简而言之即是坏字符对应的位置后面一段的后缀
     和KMP算法一样,有了好后缀我们也要移动模式串,来达到依旧部分匹配的目标。而移动的情况分为三种:
    1. 模式串中有子串匹配上好后缀
    显然,这是只需要移动模式串知道子串和好后缀重合就行了

    imag

    1. 模式串中没有子串匹配上后后缀,但存在一个最长前缀,它等于好后缀的后缀

    imag

    1. 模式串中没有子串匹配上后后缀,并且在模式串中找不到最长前缀
      这种情况是我们最喜欢的了:直接整个全部移走

    imag

    gs表

     有了之前的经验,我们很容易找到移动的方法:事先构建一个表单,上面记录了每次需要移动的距离。我们将这个表称之为gs表。
     但是gs表想要直接构建是比较困难的。具体实现的时候我们会使用一个叫做suffix表的辅助表。

    构建suffix

     suffix表是一个这样的表:

    suffix[i] = s 表示以i为边界,与模式串后缀匹配的最大长度,如下图所示,用公式可以描述:满足P[i-s, i] == P[m-s, m]的最大长度s

    imag
     构建算法较为简单:

    int * suffixes(const string & pat)
    {
        const int len = pat.length();
        int num;
        int *suff = new int[len];
        suff[len - 1] = len;
        for (int i = len - 2; i >= 0; --i)
        {
            for (num = 0; num <= i && pat[i-num] == pat[len-num-1]; ++num);
            suff[i] = num;
        }
        return suff;
    }

    构建gs

     有了suffix表之后,我们就可以构建gs表了。

    gs[i] 表示遇到好后缀时,模式串应该移动的距离,其中i表示好后缀前面一个字符的位置(也就是坏字符的位置)

     构建bmGs数组分为三种情况,分别对应上述的移动模式串的三种情况:
    - 模式串中有子串匹配上好后缀

    - 模式串中没有子串匹配上好后缀,但找到一个最大前缀

    - 模式串中没有子串匹配上好后缀,但找不到一个最大前缀

     再给出具体实现之前,首先让我们来考虑这样一个问题:如果同时存在符合条件的串中子串和前缀子串我们优先考虑那个呢?答案不言而喻:为了防止回溯,我们应该尽量让一次移动的距离少一点。所以如果有多种匹配情况:优先匹配串中子串,其次是最大前缀,最后再是移动整个模式串

    int * getGs(const string & pat)
    {
        const int len = pat.length();
        const int lastIndex = len - 1;
        int *suffix = suffixes(pat);
        int *gs = new int[len];
        //找不到对应的子串和前缀
        for (int i = 0; i < len; ++i)
            gs[i] = len;
        //找前缀
        for (int i = lastIndex; i >= 0; --i)
        {
            //存在我们想要的前缀
            if (suffix[i] == i + 1)
            {
                for (int j = 0; j < lastIndex - i; ++j)
                {
                    if (gs[j] == len)
                        gs[j] = lastIndex - i;
                }
            }
        }
        //找中间的匹配子串
        for (int i = 0; i < lastIndex; ++i)
        {
            gs[lastIndex - suffix[i]] = lastIndex - i;
        }
        delete[] suffix;
        return gs;
    }

     以上就是gs表构建的具体算法。我们注意到算法的核心部分其实是三个for循环,分别对应了:找不到对应的子串和前缀,找到了前缀,找到了中间匹配的子串。
     这里的技巧在于 for循环的安排顺序是不可调换的。注意到:如果gs[i]在三个循环流程中都有设计,那么gs[i]的值必然越来越小。通过这种安排我们就可以保证如果有在位置i有多种移动方式,那么gs[i]给出的方案一定是移动量最小的。
     在对整体的安排有了一个分析后,我们来具体分析每个循环算法中的功效。

    第一个for循环对应了移动整个模式串

    for (int i = 0; i < len; ++i)
        gs[i] = len;

     可以看到我们在这里将整个gs表都赋值为len。这是一个巧妙的处理,因为如果在i处还有更好的移动方案,那么gs[i]在后面的处理中一定会被覆盖掉。而如果不被覆盖,那就说明这种移动是合理的。例如在下图的字符a处,我们发现只要文本串中后缀对应部分还和模式串重合,就不可能匹配,所以之间将模式串移走整个距离就可以了。
    imag

    第二个for循环对应了找到了一个最大前缀

    for (int i = lastIndex; i >= 0; --i)
    {
        //存在我们想要的前缀
        if (suffix[i] == i + 1)
        {
            for (int j = 0; j < lastIndex - i; ++j)
            {
                if (gs[j] == len)
                    gs[j] = lastIndex - i;
            }
        }
    }

     这个算法较为复杂,下面展开细节分析:

    判断前缀的存在性

     这里的技巧在于如何判断前缀存在?答案是如果 suffix[i] = i+1那就说明存在这样一个前缀。所以判断条件:

    for (....)
    {
        if (suffix[i] == i + 1)
        {
    
        }
    }

     的含义就是 遍历整个模式串,一旦找到了符合前缀要求的字符就执行内部的逻辑(即填值上去)

    从后往前

     我们注意到一个很奇怪的现象,是出在最外面的for身上:

    for (int i = lastIndex; i >= 0; --i)

    为什么从后往前遍历
     我们要考虑到一点:如果存在 $i$$j$$i > j$ 都满足前缀的要求,我们选哪个?显然我们沿用刚才的思路:我们不希望一次性移动太多距离,所以如果有多个符合的选项选择能让移动距离最小的

    imag
     既然我们希望最终的结果是指向前缀的最后一个字符,那么我们就可以有两种办法:
    - 从前往后遍历,用后来者覆盖前面的内容
    - 从后往前遍历,并想办法阻止覆盖操作

     仔细比较,我们选择了后者。因为如果最大前缀很长的话,我们就会被迫执行大量垃圾操作,这回极大地影响算法的效率。而关于后者如何阻止覆盖,我们稍后再讲。

     这样我们就来到了最内层的区域:

    for (int j = 0; j < lastIndex - i; ++j)
    {
        if (gs[j] == len)
            gs[j] = lastIndex - i;
    }

    填表操作

     首先解释一下最里层的运算,也就是真正意义上的填表操作:

    gs[j] = lastIndex - i;


     为什么是lastIndex-i我们可以从上图中得出答案。不再赘述。

    找到了前缀的模式串和执行相关操作的区间

     接着我们从外向内讲。首先就是又一重的循环:

    for (int j = 0; j < lastIndex - i; ++j)

     这重循环的含义在于覆盖所有位于这块区间的gs[j]的值,让所有在该区间失配的情况下都像右移动lastIndex - i个单位。这里有两个略微需要转个弯才想明白的问题。
    - 为什么失配在不同地方却移动相同的距离
     首先,我们要明确,这只是整体处理的一个步骤。这意味着如果我们还可以找到串中子串的话,那么gs[j]值待会还要被覆盖。那么如果只能找到最大前缀的话,那他们移动的距离也都相同
     答案是是的。因为在这种情况下,只要失配的位置在目标后缀的第一个字符之前。那么具体位置毫无意义。因为根本不可能找到一个和该失配字符之后的整个后缀完全匹配的子串,所以不论停在那里,最终都只能把模式串右移lastIndex-i个单位,来让最大前缀和目标后缀对应的文本串中的子串相重合
     以下图为例,这里我们停在了字符g的位置,但这有用吗?模式串中根本不存在一个bcde的子串,只有一个cde的前缀。所以不论是停在了g处还是在f或者e处都没有区别,最终都只能移动模式串知道前缀cde和文本串中的cde匹配。换而言之——移动距离相同
    imag

    • 为什么j < lastIndex - i?
       在上一点的分析中我们有提到过这样一句话:
      “只要失配的位置在目标后缀的第一个字符之前”。
       事实上这句话就对应了j < lastIndex - i,意思是,我们的操作仅限于目标后缀之前的字符。因为目标后缀中的字符必然可以找到与自己的后缀像匹配的子串

    阻止覆盖

     前面我们讲到,为了维护算法的效率,我们选择从后往前遍历。但这会带来一个问题,就是可能存在期望值被覆盖的可能。这就要用到我们的判断条件了:

    if (gs[j] == len)

     事实上,我们还可以有其他的手段,这里就不再讲了。

    第三个for循环对应了找到一个串中子串

    for (int i = 0; i < lastIndex; ++i)
    {
        gs[lastIndex - suffix[i]] = lastIndex - i;
    }

     首先先看最里面的执行操作:

    gs[lastIndex - suffix[i]] = lastIndex - i;

    lastIndex - i好理解,就是要移动的距离。

    lastIndex - suffix[i]就很有技巧性了,它对应的位置如上图所示,下图是简化版:
    imag
     结合外层的循环:

    for (int i = 0; i < lastIndex; ++i)
    {
    
    }

     我们就可以大致看出该算法的执行逻辑:从头到尾遍历模式串,依次找到合适的位置,将然后填充其他位置的gs。我们来分析具体的细节:
    - 遍历的顺序必须是从左到右
     有了前面的基础,这个规则就很好理解了。简而言之如果lastIndex-suffix[i] == lastIndex-suffix[j]$i<j$。那么我们就可以用移动距离小的lastIndex - j覆盖移动距离大的lastIndex - i。从而保证了我们一直坚持的尽量不回溯的原则。
    - 最后一位没有列入循环
     注意到我们的循环条件i < lastIndex,也就是收最后一位并没有处理。这是因为suffix[lastIndex] == length,所以处理了也毫无意义。
    - 如果suffix[i] == 0
     这种情况下意味着pat[i] != pat[lastIndex]那就至少需要将pat移动到一个使新比较的字符和之前的字符不同的位置

    改进BM主算法

     有了好后缀之后,我们就可以改进主算法了:

    patAt += max(gs[cmp], cmp - bc[text[patAt + cmp]]);

     由于gc[cmp]必定大于零,所以就可以避免了使用bc表时后退的情况。
     同时由于两者的移动都是合理的,所以我们不妨选择在合理范围内更加大的移动量以提高算法效率。(注意此前我们强调要让移动距离尽可能小是因为无法确定更大的移动是否是合理的)

    最终算法

    int bmMatch(const string & text, const string & pat)
    {
        int *bc = getBc(pat);
        int *gs = getGs(pat);
        //patAt指向了当前pat和text对齐的位置
        int patAt = 0;
        //cmp指向了当前比较的位置
        int cmp;
        const size_t PATLASTID = pat.length() - 1;
        const size_t patLen = pat.length();
        const size_t textLen = text.length();
        while (patAt + patLen <= textLen)
        {
            //如果匹配成功,cmp就会来到-1的位置上
            //patAt + cmp 指向了text上当前比较的字符
            for (cmp = PATLASTID; cmp >= 0 && pat[cmp] == text[patAt + cmp]; --cmp);
    
            if (cmp == -1)
                break;
            else
            {
                patAt += max(gs[cmp], cmp - bc[text[patAt + cmp]]);
            }
    
        }
        delete[] bc;
        delete[] gs;
        return (patAt + patLen <= textLen)? patAt : -1;
    }
    int * getBc(const string & pattern)
    {
        //256是字符表的规模大小(ACSII)
        int *bc = new int[256];
        int len = pattern.length();
    
        for (int i = 0; i < 256; ++i)
            bc[i] = -1;
    
        for (int i = 0; i < len; ++i)
        {
            bc[pattern[i]] = i; 
        }
        return bc;
    }
    int * suffixes(const string & pat)
    {
        const int len = pat.length();
        int num;
        int *suff = new int[len];
        suff[len - 1] = len;
        for (int i = len - 2; i >= 0; --i)
        {
            for (num = 0; num <= i && pat[i-num] == pat[len-num-1]; ++num);
            suff[i] = num;
        }
        return suff;
    }
    int * getGs(const string & pat)
    {
        const int len = pat.length();
        const int lastIndex = len - 1;
        int *suffix = suffixes(pat);
        int *gs = new int[len];
        //找不到对应的子串和前缀
        for (int i = 0; i < len; ++i)
            gs[i] = len;
        //找前缀
        for (int i = lastIndex; i >= 0; --i)
        {
            //存在我们想要的前缀
            if (suffix[i] == i + 1)
            {
                for (int j = 0; j < lastIndex - i; ++j)
                {
                    if (gs[j] == len)
                        gs[j] = lastIndex - i;
                }
            }
        }
        //找中间的匹配子串
        for (int i = 0; i < lastIndex; ++i)
        {
            gs[lastIndex - suffix[i]] = lastIndex - i;
        }
        delete[] suffix;
        return gs;
    }
    展开全文
  • BM 算法

    千次阅读 2013-05-28 14:49:00
    看完上次的kmp后准备看BM算法, 但是一直都没有时间,感觉,看网上的一些原理解释并不能看的很懂,然后看了就迷迷糊糊的,现在总结一下,顺便是理清思路!不知道自己会不会讲的清楚一点!( 至于代码,自己写的还在...


    看完上次的kmp后准备看BM算法, 但是一直都没有时间,感觉,看网上的一些原理解释并不能看的很懂,然后看了就迷迷糊糊的,现在总结一下,顺便是理清思路!不知道自己会不会讲的清楚一点!( 至于代码,自己写的还在测试,不知道有没有错,现在贴上来的是参照snort中的代码!虽然网上的很多代码都是这个!不过后来会写上自己的代码的 )


    BM 算法思路:

    1:

    BM算法是整体字串是从左往右移动,但是一旦字串停在某个位置时候,实际的匹配是从右往左的,例如:

    原串:A B C E C A B E

    字串:A B C A B

    停在此处,那么匹配从右往左开始,即:

    原串:A B C E C A B E

    字串:A B C A B

    <<<---------------------

     

    一旦一个字符不匹配的时候,(我们称这个字符为“坏字符”),我们采取两种办法即

    坏字符规则 和好后缀规则来确定字串到底要整体往右移动几个距离,然后再来进行从右往左的比较!所以编程的时候肯定是有两个函数分别返回当前情况需要向右移动几个单位,我们取两个中的较大的移动长度即可!

     

     下面,来详细介绍一下坏字符规则 和好后缀规则

     

    “坏字符规则“:

    例如:

    原串:A B C E C A B E

    字串:A B C A B              图一

    有个坏字符!

    我们需要怎么处理呢?

    有两条规则:

    《1》. 在原串中,若那个坏字符在字串中没有,那么在原串中从此字符开始的strlen(子串)个长度的串不可能与字串匹配!所以直接跳过该坏字符,即需要移动的长度是字串首字符到字串中对应的坏字符长度!(具体见下面第二个例子)

    《2》. 若那个坏字符在未进行匹配的剩余子串中能找到,那么在剩余子串中找到最右边的那个字符,然后与该字符对齐。

    对于上面的例子:

    C在字串中从右开始的第三个位置出现的,那么移动长度为5 – 3 = 2

    A  B   C   E   C   A   B   E

    -------  A   B   C   A   B                          (图二)

    此时我们发现:

    A B  C  E  C A  B  E                            (图三)

    --------- A  B  C  A  B

    又出现坏字符,若使用“坏字符规则”,那么我们寻找E是否在字串中出现,我们发现没有找到,那么移动后为:

    A B  C  E  C A  B  E                             (图四)

    ------------- A  B  C  A  B

     

    即:跳过此坏字符即可!!!

     

    (  在看代码的时候注意一下就ok! )

    特别注意:在算法中有这么一段,之前得到了“坏字符表”,在处理往后移动的时候是:

    i +=  max( bad_char_table[(unsigned char)str[tmp]] -x, good_suffix_table[j] );

    (x是后缀已经匹配的长度)

    (str是原串)

    (bad_char_table是坏字符表)

    (good_suffix_table是好后缀表)

    (tmp是当前指针所在原串中的下标,即坏字符下标)

    (j是字串中当前匹配坏字符的那个位置)

    不清楚代码没有关系,随后再看。

    看代码的时候注意:此处要减去一个x是必须的。因为上面说的很清楚了,是在尚未进行匹配的的剩余子串中!

     

    ===》那么我们在编程的时候需要怎么做?

    从上面我们知道,字串中没有出现的字符若是坏字符,那么直接向右移动strlen(子串)长度即可!对于出现的字符,我们知道是以最右边出现的第一个字符为基准的(也就是说,字串中有几个相同的字符,那么也是要以最右边的那个字符位置来定移动长度),所以,对于所有的字符,以及其移动的长度,我们都是可以提前预测到的!

    我们知道:字符共256个,那么定义个int数组a[256]  (所以的ASCII码都包含在内),对于字串中没有出现的直接赋值为strlen(子串),对于字串中有的字符,按照右边位置进行处理即可!

     

     

    下面看看:

    “好后缀规则”

     


    对于串:

    A B  C  E  C  A  B  E A  B  C

    ------ A  B  C  A  B

    所谓好后缀,就是后面有一部分小串是匹配的,前面有不匹配的而已!

    那么需要遵循什么规则呢?也有2点规则

     

    《1》. 在子串中,若当前的后缀在前面也是有的( 但是还有一个条件是之前的一个字符不再匹配!如下面的D和E ),例如

           XX X X  X X  X  X M  A  B C  D

             E A  B  C  D   D D  A  B  C  D

    那么,将前面的串移动到后面既可以:

           XX X X  X X  X  X X  A  B  C  D

                                      E  A  B  C  D  D  D A  B  C  D

     

    很好理解,若之前一个字符还是相同的,那么和本次的情况还是一样的,没有好转,若不相同,那么还是有机会匹配到这个坏字符的!


    《2》.如果上面的没有结果,那么就找子串中尚未进行匹配的部分的前缀尽可能大的匹配 "好后缀" 的后缀

     

    例如:

    原串:A  B  C  E  C  A  B E

    子串:         A  B  C  A  B

     

    可以很清楚的看到,C A B 在前面没有匹配了,那么只能是第二种情况,看到未匹配的前缀和已经匹配的后缀最大的匹配就是 A B,那么移动:

    原串:A  B  C E  A  B  E

    子串:                     A  B  C  A  B

     

     

    ===》那么我们在编程的时候需要怎么做?

    我们知道只要字串确定了,那么所有的什么前后所谓的匹配也是确定了的,所有也可以建立一个表,预先得到:当遇到那个后缀的时候,怎么去移动!那么需要定义一个数组

    b[], 其长度就是字串的长度,为什么呢,因为b[0]保存的是后面整个长度后缀时候需要移动的长度,…..b[len-1]保存的就是最后一个字符长度的后缀时候需要移动的距离!

     

     

    然后在遇到不匹配的时候,从两个数组中取相应的值,取两个中较大的一个进行移动即可!

     

    上面就是原理,不知道有没有说清楚~


    好的,最后冷静一下,总结一下:其实总体的思路就是提前建好“坏字符”表和“好后缀”, 然后进行BM算法,当遇到字符不匹配时候, 就需要决定整体字串应该向右边移动几位,所以需要查两个表,然后取其中大的值,就是字串移动的距离!


    下面就是代码(参考snort),后期会贴上自己的代码

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <assert.h>
    
    // max函数
    // 
    int get_max( int a, int b )
    {
    	return ( a > b ? a : b );
    }
    
    // 得到坏字符表
    // 
    // 参数:
    //		sub_str:匹配串
    //		len:匹配串长度
    //		bad_char_table:保存坏字符表
    //
    void get_bad_char_table( char sub_str[], int len, int bad_char_table[] )
    {
    	int i = 0;
    	int tmp_len = len;
    
    	// 初始化坏字符表,256个单元全部初始化为len
    	// 
    	for( i = 0; i < 256; ++i )
    	{
    		bad_char_table[i] = len;	// 即不在的字符跳过此区域,也就是向后移动匹配串长度个字符(即pLen)
    	}					// 存在的字符下面在处理
    	
    	while( len )
    	{
    		bad_char_table[(int)*sub_str++] = --len;	// (int)*sub_str转化成字符的ASCII码而已
    	}												// 下面就是遇到不匹配,但是在字串中,需要移动几个单位
    }
    
    // 下面计算 "好后缀" 好后缀表
    //
    // 参数:
    //		sub_str:匹配串
    //		len:匹配串长度
    //		good_suffix_table:保存好后缀表
    //
    void get_good_suffix_table( char sub_str[], int len, int good_suffix_table[] )
    {
    	
    	int  *sptr = good_suffix_table + len - 1;	// 方便为好后缀表进行赋值的指针
    	char *pptr = sub_str + len - 1;			// 记录好后缀表边界位置的指针
    	char c;						// 保存最后一个字符
    	char *p1, *p2, *p3;
    
    	c = *( sub_str + len - 1 );	
    	*sptr = 1;
    	pptr--;										// 边界移动到倒数第二个字符
    
    	while( --sptr >= good_suffix_table )		//该最外层循环完成给好后缀表中的每一个单元进行赋值的工作
    	{
    		p1 = sub_str + len - 2;			// 倒数第二个字符
    		
    		do
    		{
    			while( p1 >= sub_str && *p1-- != c );	// 该空循环,寻找与最后一个字符c匹配的字符所指向的位置
    		
    			if( p1 < sub_str )			// 没有找到
    			{
    				*sptr = len;			// 没有找到那么只能是len长度
    				break;
    			}
    
    			p2 = sub_str + len - 2;		// 倒数第二个字符
    			p3 = p1;			// 当前第一个匹配的字符位置( 从右往左的 )
    
    			while( p3 >= sub_str && *p3-- == *p2-- && p2 >= pptr );	// 该空循环,判断在边界内字符串匹配到什么位置
    																	// 即得到最长匹配 
    			if( p2 < pptr )	// 这是当前要求长度的后缀已经匹配完成
    			{
    				if( *++p3 == *++p2 )				// 
    				{
    					*sptr = p2 - p3;
    					break;
    				}
    				
    				if( *p2 == *p3 )// 注意为什么会有这一步:对应原理中:后缀完全匹配,但是要求,之前的一个字符是不相同的才OK
    				{
    					continue;
    				}
    			}
    
    			if( p3 < sub_str )		// 原串匹配到头
    			{
    				*sptr = p2 - p3;
    				break;
    			}
    
    		}while( p3 >= sub_str );
    		
    		pptr--;					// 边界继续向前移动
    	}
    	
    }
    
    // 下面就是BM处理
    // 参数:见上面两个函数
    // 
    int bm_search( char str[], int len1, char sub_str[], int len2, int bad_char_table[], int good_suffix_table[] )
    {
    	int i = len2;		// 用来计算移动的距离
    	int j, tmp, x;
    
    	if ( len2 == 0 )
    	{
    		return -1;
    	}
    
    	while( i <= len1 )	// 匹配尚未结束
    	{
    		j = len2;
    		tmp = i;		// 又一次开始匹配的位置
    		x = 0;
    
    		while ( str[--tmp] == sub_str[--j] )	// 看当前是否匹配
    		{
    			++x;
    
    			if ( j == 0 )			// 匹配串匹配结束
    			{
    				return i - len2;	// 第一个字符匹配位置
    			}
    		}
    		
    		i += get_max( bad_char_table[(unsigned char)str[tmp]] - x, good_suffix_table[j] );	// 计算应该向后移动多少位置
    	}								// 
    	
    	return -1;
    }
    
    // MAIN函数
    // 
    int main()
    {
    	char	str[1000];//="9634ghvecn  eirfqo fhoroe o e ovqherf938g4fh00000000@#$%^&*wo dwef";
    	char	sub_str[100];//="ovqher";
    	int		*bad_char_table = NULL;
    	int		*good_suffix_table = NULL;
    	int		idx;
    	
    	printf("\n输入原串:");
    	gets( str );
    
    	printf("\n输入匹配串:");
    	gets( sub_str );
    	
    	// 下面为256个字符分配坏字符表空间
    	//
    	bad_char_table = ( int* )malloc( 256 * sizeof( int ) );
    	assert( bad_char_table != NULL );
    
    	// 下面为"好后缀"分配表空间
    	// 
    	good_suffix_table = ( int* )malloc( strlen( sub_str ) * sizeof( int ) );
    	assert( good_suffix_table != NULL );
    
    	// 下面计算 "坏字符" 坏字符表
    	// 
    	get_bad_char_table( sub_str, strlen( sub_str ), bad_char_table );
    
    	// 下面计算 "好后缀" 好后缀表
    	//
    	get_good_suffix_table( sub_str, strlen( sub_str ), good_suffix_table );
    
    	// 下面就是BM处理
    	// 
    	idx = bm_search( str, strlen( str ), sub_str, strlen( sub_str ), bad_char_table, good_suffix_table );
    
    	if ( idx == -1 )
    	{
    		printf("没有可以匹配的串!\n");
    	}
    	else
    	{
    		printf("第一个匹配的位置是(下标从0开始):%d\n", idx);
    	}
    	
    	// 下面回收资源
    	// 
    	if ( bad_char_table )
    	{
    		free( bad_char_table );
    		bad_char_table = NULL;
    	}
    
    	if ( good_suffix_table )
    	{
    		free( good_suffix_table );
    		good_suffix_table = NULL;
    	}
    
    	return 0;
    }
    
    
    




    展开全文
  • bm算法

    千次阅读 2013-07-29 20:50:56
    BM算法在移动模式串的时候是从左到右,而进行比较的时候是从右到左的。 常规的匹配算法移动模式串的时候是从左到右,而进行比较的时候也是是从左到右的,基本框架是: [cpp] view plaincopy

    1、概述

    在用于查找子字符串的算法当中,BM(Boyer-Moore)算法是目前相当有效又容易理解的一种,一般情况下,比KMP算法快3-5倍。

    BM算法在移动模式串的时候是从左到右,而进行比较的时候是从右到左的。

    常规的匹配算法移动模式串的时候是从左到右,而进行比较的时候也是是从左到右的,基本框架是:

    [cpp]  view plain copy
    1. j = 0;  
    2.   
    3. while(j <= strlen(主串)- strlen(模式串)){  
    4.     for (i = 0;i < strlen(模式串) && 模式串[i] == 主串[i + j]; ++i)  
    5.         ;   
    6.     if (i == strlen(模式串))  
    7.         Match;  
    8.     else   
    9.         ++j;  
    10. }  

     

    而BM算法在移动模式串的时候是从左到右,而进行比较的时候是从右到左的,基本框架是:

    [cpp]  view plain copy
    1. j = 0;   
    2. while (j <= strlen(主串) - strlen(模式串)) {   
    3.    for (i = strlen(模式串) - 1; i >= 0 && 模式串[i] ==主串[i + j]; --i)   
    4.       if (i < 0)  
    5.           match;  
    6.        else   
    7.           ++j;  
    8. }  

    显然BM算法并不是上面那个样子,BM算法的精华就在于++j

    2、BM算法思想

    BM算法实际上包含两个并行的算法,坏字符算法和好后缀算法。这两种算法的目的就是让模式串每次向右移动尽可能大的距离(j+=x,x尽可能的大)。

     

    几个定义:

    例主串和模式串如下:

    主串  :  mahtavaatalomaisema omalomailuun

    模式串: maisemaomaloma

    好后缀:模式串中的aloma为“好后缀”。

    坏字符:主串中的“t”为坏字符。

    好后缀算法

    如果程序匹配了一个好后缀, 并且在模式中还有另外一个相同的后缀, 那

    把下一个后缀移动到当前后缀位置。好后缀算法有两种情况:

    Case1:模式串中有子串和好后缀安全匹配,则将最靠右的那个子串移动到好后缀的位置。继续进行匹配。

    wps_clip_image-979

    Case2:如果不存在和好后缀完全匹配的子串,则在好后缀中找到具有如下特征的最长子串,使得P[m-s…m]=P[0…s]。说不清楚的看图。

    wps_clip_image-1152

    坏字符算法

    当出现一个坏字符时, BM算法向右移动模式串, 让模式串中最靠右的对应字符与坏字符相对,然后继续匹配。坏字符算法也有两种情况。

    Case1:模式串中有对应的坏字符时,见图。 
    wps_clip_image-1349

    Case2:模式串中不存在坏字符。见图。

    wps_clip_image-1472

    移动规则

    BM算法的移动规则是:

    将概述中的++j,换成j+=MAX(shift(好后缀),shift(坏字符)),即

    BM算法是每次向右移动模式串的距离是,按照好后缀算法和坏字符算法计算得到的最大值。

    shift(好后缀)和shift(坏字符)通过模式串的预处理数组的简单计算得到。好后缀算法的预处理数组是bmGs[],坏字符算法的预处理数组是BmBc[]。

    3、代码分析
    定义

    BM算法子串比较失配时,按坏字符算法计算模式串需要向右移动的距离,要借助BmBc数组。

    注意BmBc数组的下标是字符,而不是数字

     

    BmBc数组的定义,分两种情况。

    1、 字符在模式串中有出现。如下图,BmBc[‘k’]表示字符k在模式串中最后一次出现的位置,距离模式串串尾的长度。

    2、 字符在模式串中没有出现:,如模式串中没有字符p,则BmBc[‘p’] = strlen(模式串)。

    wps_clip_image-1885

    BM算法子串比较失配时,按好后缀算法计算模式串需要向右移动的距离,要借助BmGs数组。

    BmGs数组的下标是数字,表示字符在模式串中位置。

    BmGs数组的定义,分三种情况。

    1、 对应好后缀算法case1:如下图:i是好后缀之前的那个位置。

    wps_clip_image-2036

    2、 对应好后缀算法case2:如下图所示:

    wps_clip_image-2086

    3、 当都不匹配时,BmGs[i] = strlen(模式串)

    wps_clip_image-2145

    在计算BmGc数组时,为提高效率,先计算辅助数组Suff。

    Suff数组的定义:suff[i] = 以i为边界, 与模式串后缀匹配的最大长度,即P[i-s...i]=P[m-s…m]如下图:

    wps_clip_image-2272

    举例如下:

    wps_clip_image-2380

    分析

    用Suff[]计算BmGs的方法。

    1) BmGs[0…m-1] = m;(第三种情况)

    2) 计算第二种情况下的BmGs[]值:

    for(i=0;i

    if(-1==i || Suff[i] == i+1)

    for(;j < m-1-i;++j)

    if(suff[j] == m)

    BmGs[j] = m-1-i;

    3) 计算第三种情况下BmGs[]值,可以覆盖前两种情况下的BmGs[]值:

    for(i=0;i

    BmGs[m-1-suff[i]] = m-1-i;

    如下图所示:

    wps_clip_image-2697

    Suff[]数组的计算方法。

    常规的方法:如下,很裸很暴力。

    Suff[m-1]=m;

    for(i=m-2;i>=0;--i){

    q=i;

    while(q>=0&&P[q]==P[m-1-i+q])

    --q;

    Suff[i]=i-q;

    }

    有聪明人想出一种方法,对常规方法进行改进。基本的扫描都是从右向左。改进的地方就是利用了已经计算得到的suff[]值,计算现在正在计算的suff[]值。

    如下图所示:

    i是当前正准备计算的suff[]值得那个位置。

    f是上一个成功进行匹配的起始位置(不是每个位置都能进行成功匹配的,  实际上能够进行成功匹配的位置并不多)。

    q是上一次进行成功匹配的失配位置。

    如果i在q和f之间,那么一定有P[i]=P[m-1-f+i];并且如果suff[m-1-f+i]=i-q, suff[i]和suff[m-1-f+i]就没有直接关系了。

    wps_clip_image-3177

    代码

    [cpp]  view plain copy
    1. void preBmBc(char *x, int m, int bmBc[]) {  
    2.   
    3.    int i;  
    4.   
    5.    for (i = 0; i < ASIZE; ++i)  
    6.   
    7.       bmBc[i] = m;  
    8.   
    9.    for (i = 0; i < m - 1; ++i)  
    10.   
    11.       bmBc[x[i]] = m - i - 1;  
    12.   
    13. }  
    14.   
    15. void suffixes(char *x, int m, int *suff) {  
    16.   
    17.    int f, g, i;  
    18.   
    19.   f = 0;  
    20.   
    21.    suff[m - 1] = m;  
    22.   
    23.    g = m - 1;  
    24.   
    25.    for (i = m - 2; i >= 0; --i) {  
    26.   
    27.       if (i > g && suff[i + m - 1 - f] < i - g)  
    28.   
    29.          suff[i] = suff[i + m - 1 - f];  
    30.   
    31.       else {  
    32.   
    33.          if (i < g)  
    34.   
    35.             g = i;  
    36.   
    37.          f = i;  
    38.   
    39.          while (g >= 0 && x[g] == x[g + m - 1 - f])  
    40.   
    41.             --g;  
    42.   
    43.          suff[i] = f - g;  
    44.   
    45.       }  
    46.   
    47.    }  
    48.   
    49. }  
    50.   
    51. void preBmGs(char *x, int m, int bmGs[]) {  
    52.   
    53.    int i, j, suff[XSIZE];  
    54.   
    55.    suffixes(x, m, suff);  
    56.   
    57.    for (i = 0; i < m; ++i)  
    58.   
    59.       bmGs[i] = m;  
    60.   
    61.    j = 0;  
    62.   
    63.    for (i = m - 1; i >= 0; --i)  
    64.   
    65.       if (suff[i] == i + 1)  
    66.   
    67.          for (; j < m - 1 - i; ++j)  
    68.   
    69.             if (bmGs[j] == m)  
    70.   
    71.                bmGs[j] = m - 1 - i;  
    72.   
    73.    for (i = 0; i <= m - 2; ++i)  
    74.   
    75.       bmGs[m - 1 - suff[i]] = m - 1 - i;  
    76.   
    77. }  
    78.   
    79. void BM(char *x, int m, char *y, int n) {  
    80.   
    81.    int i, j, bmGs[XSIZE], bmBc[ASIZE];  
    82.   
    83.    /* Preprocessing */  
    84.   
    85.    preBmGs(x, m, bmGs);  
    86.   
    87.    preBmBc(x, m, bmBc);  
    88.   
    89.    /* Searching */  
    90.   
    91.    j = 0;  
    92.   
    93.    while (j <= n - m) {  
    94.   
    95.       for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);  
    96.   
    97.       if (i < 0) {  
    98.   
    99.          OUTPUT(j);  
    100.   
    101.          j += bmGs[0];  
    102.   
    103.       }  
    104.   
    105.       else  
    106.   
    107.          j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);  
    108.   
    109.    }  
    110.   
    111. }  

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,612
精华内容 6,644
关键字:

bm算法