监控项目分析-关键算法

本设计中有两个关键性算法,分别为机器过滤中的关键词匹配与指定时间段内的防重复算法。其中关键词的匹配算法最为重要,因为它是机器审核的主干部分,即内容过滤。

关键词匹配算法:GNU-grep (作者Mike Haertel),水很深呢,之前一直以为是AC自动机,看样子有东西啃了。下面是有用的链接:

  1. http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html
  2. http://blog.sina.com.cn/s/blog_593e03920100fv4v.html
  3. http://fob.po8.org/node/173
  4. http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
  5. http://www.cppblog.com/mythit/archive/2011/12/01/80633.html
  6. http://stblog.baidu-tech.com/?p=418

首先把自动机kmp的原理再复习一下,以助于理解BM算法。这两个算法虽然都是单模匹配,但是其优化匹配思想与BM算法是一致的。

看完BM算法的PPT,有一种想法索绕在脑海中:各种问题的最优处理方法都客观存在那儿,就看你能不能发现。有点废话。言归正传,还是说BM的学习过程吧。

首先BM与前期学习的所有的匹配算法有一个最大的不同,其一改人们的正常思维(匹配串从左向右与目标串进行比较,换句话说就是前向比较),改成匹配串从右向左与目标串进行比较。为什么要打破常规处理方法,这种处理果真能提高处理效率吗?先保留这些疑问,我们再分析下字符串比较的过程。
想想匹配动作什么时候算是成功匹配呢?那当然是匹配串的最后一个字符匹配成功。如果我们上来就判断最后一个是否匹配成功,如果失败,那么不就省略了匹配串前面的所有字符的匹配动作了吗!这是什么效率呢。可是仔细想想,还是有些问题需要处理。好,下面开始讲解BM的Bad Charactor Rule

为了更好的展开讨论,先形式化要处理的问题:

  1. P表示匹配串,
  2. T表示目标串,
  3. Σ表示P的字符集合,
  4. n表示P的长度,
  5. x表示某个字符,
  6. R(x) = max ({0} ∪ {i < n | P [i] = x}),R(x)用自然语言来描述:即寻找x在P的最右出现位置,如果没有出现,则为0位置。
.......abcfsea.....
         case 蓝色代表匹配成功/红色代表匹配失败

观察上面的匹配动作,如果在目标串遇到一个字符x不仅与当下的匹配串的字符匹配失败,而且与Σ中的任何一个字符都会匹配失败,也就是说匹配串不含有字符x。那么很明显,x前面(包括自己),都无需参与匹配了。如下图所示,匹配串整体右移到x的右边:

.......abcfsea.....
           case

那么如果匹配失败的字符x存在于匹配串P中的j位置呢(此时P的匹配位置为i,即在P[i]匹配失败)立即会想到的是,将P[j]与字符x对齐,而且如果x在P中多次出现,应该选择那个最右边的,即如下所示:

.......abccass.....
         cass
.......abccass.....
          cass

但仔细一想,有问题,如下图:

.......abccaas.....
         casa

如果按照上面的规则,岂不是倒退回去了,显然不能这样做呢。因此就需要判断,j与i的关系:

  1. i>j,那么皆大欢喜,可以直接对齐;
  2. i<j,那么就悲剧了,比较的复杂的处理方法,是对P中出现x的索引进行存储,每次去找那个小于i的‘j’。比较简单的处理方法是右移一个单位,最原始的匹配方法。

总结上面的处理方法,就是Bad Charactor Rule,i为匹配失败时P的索引,此时目标串的字符为x,j为P中x的最右索引位置,那么当匹配失败时P的向右移动的字符数为:

  1. i>j,移动R(x)
  2. i<j,移动1(使用简单的处理方法)

Bad Charactor Rule讲完了,可是前面的KMP与自动机的字符串匹配思想还是没有使用呢,即当匹配失败时利用已经匹配的信息来尽量右移P。

BM虽然是后向比较,但它有在匹配成功一段后,遇到一个匹配失败字符。那么后面那段匹配成功的串就是可以利用。但BM有一点不同之处,且看下面讲解:

......afdofadcdcese.....
         oseasecase

se是匹配成功的串,如果按照KMP与自动机的思想,P移动如下:

......afdofadcdcese.....
             oseasecase

可是我们发现,这必然会匹配失败,因为se的右侧还是为a,和刚才匹配失败的原因是相同。我们无法预知到目标串会是什么样子,但我可以知道匹配串,我们把那些拥有相同首字符的相同子串认为不能作为下次移动的匹配,即如上图中有三个se,只有第一个与第三个才能作为KMP与自动机认为‘相同’的串,为什么第二个不行呢,因为当第三个失败时,是因为a匹配失败,如果使用第二个,同样会因为a匹配失败。

如果已经匹配的部分,作为整体在P除自身外未再出现,怎么办呢?

寻找P的最大相同前缀与已经匹配部分(也是P)的后缀,进行对齐。

如果寻找失败,那就更好处理了,这说明除了刚才匹配成功的部分(而且这部分虽然是匹配成功了,但已经不能继续向前匹配了),已经匹配部分没有任何子串能够与P匹配,连一个字符也没有。P整体右移n个单体,即略过已经匹配的部分。

好规则即:对于匹配失败后如何利用已经匹配部分来获得最少回溯简单说来就是两条

  1. 与KMP相同的规则,寻找‘匹配’部分后缀与模式串本身前缀的最大相同部分
  2. 寻找匹配部分(设为:x***),与其前面部分的中出现最右对应串为(~x***)

其中,以2出来的优先级高

上面就是BM(Boyer-Moore)算法的基本思想,下面先来简单介绍下grep中的MP算法的实现思路:

  1. 对所有的模式串构建平衡字典树;
  2. 利用BM算法,构建查找失败时的next值

本来打算用一个上午实现BM的,结果思路有了代码写了两个小时还没有出来,这就是典型的眼高手低吧!借助wiki上的C实现,才得以用python实现了BM,而且坏规则用的还是上面描述的最简单的一种,甚至还要简单:实际上只对尾字符进行坏规则运用,这样也就不需要比较i与j的大小了,因为如果此时T的字符为x,且出现在P(肯定不是最后一个,因为匹配失败了),那么必然此时的j>i,因为j是len(P)!!!

def make_delta2(delta2,pattern):
    pattern_len = len(pattern)
    last_prefix_index = pattern_len - 1

    #case 1:kmp table
    for i in range(pattern_len-1,-1,-1):
        n = i+1
        if pattern[n:]==pattern[:pattern_len-n]:
            last_prefix_index = n
        delta2[i] = pattern_len-1-i + last_prefix_index

    #case 2:update the delta2 with ~x***
    for i in range(0,pattern_len):
        j = 0
        for j in range(0,i):
            if pattern[i-j] != pattern[pattern_len-1-j]:break #从后向前比较
        if pattern[i-j]!=pattern[pattern_len-1-j]:
            delta2[pattern_len-1-j] = pattern_len-1-i+j

最精巧的就是构造delta2,即好规则运用。按照上面的讲解类KMP最大前缀的优先级要低于寻找~x****串,为什么呢?

  1. 因为最大前缀如果使用,那么整个串的移动距离显然大于中间匹配上~x****时移动的距离
  2. 更简单的理解就是,尽量不要遗漏任何可能的匹配

好了,优先级好做,先处理前缀呗,后面处理~x***若产生结果再覆盖前面的结果就可心实现。

对于处理~x****过程中,还需要遵守第二条:尽量不要遗漏任何可能的匹配。如何去寻找~x***,而且在有多个存在时,要使用最右边的。可以分成两部分:

  1. 先寻找~x***中的***,也就是可匹配部分,这与前面的KMP不同的是:****不一定非得是P的前缀,中间某一段也是OK的。
  2. 我们注意到**** 在P是这样的分布的:&&&****&&&&****&&...****,不管前面出现多少个,最后一个总是后缀(而且事先并不知道其长度)。那么我们就采用从后向前进行比较来获得段P的前缀中,其后缀与P的后缀的最长相同部分。
  3. 2完成了,再比较两者前面的字符是否相同就完成了delta2分析了。

发表评论