WM(Wu-Manber)算法详解及C语言实现程序代码解析参考

WM算法采用字符块技术，增大了主串和模式串不匹配的可能性,从而增加了直接跳跃的机会。使用散列表选择模式串集合中的一个子集与当前文本进行完全匹配。使用前缀表进一步过滤不匹配的模式串，使算法获得了较高的运行效率。

WM算法首先对模式串集合进行预处理。预处理阶段将建立3个表格：SHIFT表，HASH表和PREFIX表。SHIFT表用于在扫描文本串的时候，根据读入字符串决定可以跳过的字符数，如果相应的跳跃值为0，则说明可能产生匹配。HASH表用来存储尾块字符散列值相同的模式串。PREFIX表用于存储尾块字符散列值相同的模式串的首块字符散列值。

假设模式串集合P中最短的模式长度为m，那么，后续仅考虑所有模式的前m个字符组成的模式串。

设X=x1…xB为T中的待比较的长度为B的子串，通过hash函数映像得到一个索引值index，以该索引值作为偏移得到SHIFT表中的值，该值决定读到当前子串x后可以跳过的位数。假设X映射到SHIFT表的入口为index的表项，即index=hash(x)。

SHIFT表中值的计算原则为：

（1）       如果X不出现在模式串中，则SHIFT[h]=m-B+1。

（2）       如果X出现在某些模式串中，而且在所有的模式串中的最右出现位置为q，则SHIFT[h]=m-q。

算法匹配的大致原理：

（1）       设当前比较的文本串X的hash值为h。如果SHIFT[h]=0，说明可能产生了匹配，那么需要进一步的判断。

（2）       用该h值作为索引，查HASH表找到HASH[h]，它存储的是指标，指向两个单独的表：一个是模式链表，另一个是PREFIX表。模式链表中存放的是后B个字符的hash值同为h的所有模式。

（3）       对于待比较长度为m的串，如果其长度为B的前缀与模式的前缀的hash值也相同，则再将相应的文本串与符合的模式逐一进行比较，最终判定是否完全匹配。

算法匹配的主要过程：

基于后缀的模式匹配，每次扫描B个字符T[m-B+1]…..T[m]。

（1）       扫描text的末B位T[m-B+1]…..T[m]通过hash function计算其哈希值h。

（2）       查表，SHIFT[h]>0，text小指针后滑SHIFT[h]位，执行（1）；SHIFT[h]=0，执行那个（3）。

（3）       计算此m位text的前缀的哈希值，记为text_prefix。

（4）       对于每个p（HASH[h]≦p<HASH[h+1]），看是否PREFIX[p]=text_prefix。

（5）       如果相等，让真正的模式串去和text匹配。

  WM算法的代码参考：

下面给出对这份代码的详细注释以及流程图。

共包含wm.h文件和wm.c文件，首先给出的是对代码的详细注释：

 具体请参考附件

程序代码的流程图解析

下面部分为程序代码的流程图解析，有助于更好的理解上面的程序

Main()

{

WM_STRUCT* p=wmNew();--->(1)

While(n--)

    wmAddPattern(p,keyword,klength);--->(2)

wmPrepPatterns(p);---->(3)

wmSearch(p,str,slength);----->(8)

wmFree(p);---->(10)

}

(1)    new(p)以及p的初始化

(2)    keyword-----add-->p->list

(3)    plist---得到->msPatArray

sort(ps);-->(4)

wmPrepHashedpatternsGroup(ps);-->(5)

wmPrepShiftTable(ps);-->(6)

wmPrepPrefixTable(ps);--->(7)

(4)    冒泡排序，字符串哈希值从小到大排列

(5)    HASH表初始化

计算有多少个不同哈希值，且从小到大

拉链：

(6)    构建SHIFT表

SHIFT[index]=  m-B+1;//无匹配

               min(shift);//最短移动距离

(7)    构建PREFIX表

Ps->msPrefix=HASH16(ps->msPatArray.psPat);

(8)    求tshift

若tshift!=0  移动tshift

若tshift=0   hash值不存在，continue;

            wmGroupMatch--->(9)

(9)    for(;patrn<patrnEnd;patrn++)

      比较ps->msprefix[index++]和text_prefix

      若相等，再比较整个模式串

(10) free(p)

WM(Wu-Manber)算法C语言程序代码（详细注释）下载：点击下载此文件