优化的KMP算法.pptx

分布式存储的并行串匹配算法的设计与分析;Brute-Force（暴力匹配）;1,Brute-Force（暴力匹配）;首先S[1]和T[1]比较，若相等，则再比较S[2]和T[2]，一直到T[M]为止；若S[1]和T[1]不等，则S向右移动一个字符的位置，再依次进行比较。如果存在k，1≤k≤N，且S[k+1…k+M]=T[1…M]，则匹配成功否则失败。该算法最坏情况下要进行M*(N-M+1)次比较，时间复杂度为O(M*N)。;S: ababcababaT: ababaBF算法匹配的步骤如下：;;2,优化前的KMP算法;Next[]函数;;KM P算法 的关键是根据给定的模式串 W [1, m ]定义一个 N ex t函数 。 N ex t函数 包含了模式串本身局部匹 配的信息 。 Nex t 函数的定义如下: ;S: cbaccbacbbT: cbacbKMP算法匹配的步骤如下：;c;3,优化后的KMP算法（分布式串匹配）;算法:N ex t函数和 New nex t函数的计算算法 输入: 模式串 W [1, m ]输出:next [1, m+ 1 ]和 newnext [ 1, m ] pro cedure N EX Tbeginnext [ 1]= newnext [1]= 0j= 2while j = m+ 1 doi= next [j- 1]w hile (i! = 0 and W [i ]! = W [j - 1] ) doi= next [i ] endwhilenext [j ]= i+ 1 if j! = m+ 1if W [j ]! = W [i+ 1 ]newnext [j ]= i+ 1elsenewnext [ j ]= newnext [i+ 1 ] endifendifj+ + endwhileend;3.1实验结果;b,通信时间的分析 不同周期、不同处 理器数和不同文本串长情况下的通信时间 曲线 ;对 每一组周期串长和处 理器数的组合求出 平均通信时间 , 画出它们与 周期和处 理器数的关 系图;总结：在分布 式存储系统中 , 由于文本串的分 布存储和模式串的 局部存储 ,使 得并行串 匹配算法必 须在尽可 能降 低通信开销的情况下处理段间匹配 . 论文中给出的算法很好地解决了这个问题 , 不仅通信复杂度 很小 ,计算 复杂度 也达到了最优 , 而且还具有较好的可扩展性 。