字符串算法ppt课件.ppt

《字符串算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章字符串处理算法邹权（博士）计算机科学系6.1问题介绍6.2Z-box算法6.3BM算法6.4KMP算法6.5关键字树6.6后缀树提要6.1问题介绍问题提出：字符串精确匹配（ExactStringMatching）问题可以描述如下：给定一个长字符串T和一个短字符串P，其中它们的长度分别是

2、T

3、=m,

4、P

5、=n，利用最理想的时间和空间找出全部的T中与P完全匹配的子串。习惯的表示方法：字符串T/P中的第i个字符用T(i)来表示。6.2Z-box算法[定义]Zi(S)表示在字符串S中从第i位起与S的前缀匹配的最长的字符串的长度。

6、（数值）注：如果S在上下文中很明显，Zi(S)可以用Zi来表示。例：S=aabcaabxaaz那么12345678Z5(S)=3；Z6=1；Z7=Z8=0Z-box：其中每个与前缀匹配的子串就叫一个Z-box。对于任意数字i，如果S（i）属于某一个Z-box，则定义Li表示该Z-box的最左端的位置，Ri表示该Z-box的最右端的位置。例：在上例中L6=5R6=7性质：ifi>j,thenRi>=Rj[任务]在线性时间内（O

7、S

8、）计算S的所有Zi[思想]Z2正常计算，然后归纳计算Zk，可以减少比较的次数[思想]令S=P$T,

9、其中$是特殊字符，在S和T中都不存在。利用Z算法计算Zi(S)。[方案]对于任意j，如果Zn+1+j(S)=n,则P出现在T(j)处。[加强]因为$的设定，对于任意i都有Zin时（即在T中）Zk值不用计算，只需要维持（maintain）R和L的值。6.3BM算法[名称]Boyer-Moore算法[特点]从左向右移动，自右向左扫描[技巧]坏字符规则好后缀规则6.3.1坏字符规则[实质]把P中的坏字符x移到T中的x的下面[定义]对于字母表中的每一个字符x，R(x)表示x在P中的最右端的位置，如果P

10、中没有x，则R(x)=0。[规则]对于P和T，如果P右面的n-i个字符都和T匹配，但是P(i)≠T(k)。那么P可以向右移动max[1,i-R(T(k)]位。1234567890[例]T=xpbctbxabpqxP=tpabxab因为P(3)!=T(5),R(T(5))=R(t)=1max[1,3-R(T(5))]=2所以P可以向右移动2位，然后再从右向左依次同T比较6.3.1坏字符规则普通坏字符规则有局限性：1.不适合简单字母表（DNA匹配）2.不适合有大量重复子串的P（蛋白质匹配）加强规则：当P(i)≠T(k)时，如果T(

11、k)=x，将P中位置i左面最近的x移到T(k)下面。（更好的体现了坏字符规则的精神）。相关讨论：普通的坏字符规则节省空间，它只需要O

12、∑

13、（∑是字母表）的空间存放R(x)(R(x)是一个数组)；而加强坏字符规则可能需要更大的空间。解决办法：可以不用二维数组，用一维数组，其中一维数组中的每个元素是一个数的序列。如：P=abacbabc那么R(a)=6,3,1所需空间O(n)6.3.2好后缀规则坏字符规则的局限：1.不适合小字母表2.最差运行时间不是线性的思想：看准T中的子串t，看P中还有没有子串匹配t区别：坏字符规则是去匹配T中

14、的一个坏字符；好后缀规则是去匹配T中的一个子串规则：给定P、T，T的子串匹配了P的一个后缀，但是再往左一个字符就不匹配了。然后寻找t`：1.t`和t相同2.t`不是P的后缀3.t`左面的那个字符同与t匹配的P的后缀的左面那个字符不相同。将P向右移，直到t`位于t的下面。如果t`不存在，则将P向右移动最少的格数使：P的前缀同t的后缀相匹配。如果这种情况也不存在，那么将P向后移动n位。如果T中发现了一个P，将P向右移动最少格数使：P的前缀能够和T中发现的P的后缀相匹配。如果没有这种匹配，则将P向后移动n位。例12345678901

15、234TprstabstubabvqxrPqcabdabdab1234567890因为P(8)！=T(10)，t=ab，又因为t`在P中开始的位置是3，所以P向右移动6步[对比]在本例中，坏字符规则只能使P向右移动1步6.4KMP算法[名称]Knuth-Morris-Pratt算法[特点]从左向右移动，从左向右比较传统的模式匹配算法缺点a≠b在第一次匹配之后就已经预知了后移一位后匹配的失败如何避免冗余匹配？冗余匹配删除！直接前移2位怎么判断匹配是冗余的？通过模式串自身信息确定冗余匹配的判断上一次匹配得到的匹配信息模式串自身的信

16、息模式串自身子串间匹配信息哪些信息？[定义]对于P中的每个位置i,spi(P)为P[1...i]中最长后缀的长度，该后缀与P的一个前缀匹配[数值][注]对于任意串sp1=0[例]12345678901P=abcaeabcabdsp2=sp3=0;sp4=1;sp8=3;sp1