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

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

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

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

X=x1…xBT中的待比较的长度为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       设当前比较的文本串Xhash值为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的末BT[m-B+1]…..T[m]通过hash function计算其哈希值h

2       查表,SHIFT[h]>0text小指针后滑SHIFT[h]位,执行(1);SHIFT[h]=0,执行那个(3)。

3       计算此mtext的前缀的哈希值,记为text_prefix

4       对于每个pHASH[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表初始化

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

拉链:

WM算法

(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语言程序代码(详细注释)下载:点击下载此文件

点赞 (0)
  1. 小菜虫说道:

    怎样改成汉字版本呢?

  2. 七七说道:

    来关注学习了!顶一个!

  3. 学夫子说道:

    全是代码,纯支持啦,呵呵
    祝愿你新年愉快

发表评论

电子邮件地址不会被公开。 必填项已用*标注