六章字符串处理算法.pptVIP

6.1 问题介绍 问题提出：字符串精确匹配（Exact String Matching）问题可以描述如下：给定一个长字符串T和一个短字符串P，其中它们的长度分别是|T|=m, |P|=n，利用最理想的时间和空间找出全部的T中与P完全匹配的子串。 习惯的表示方法：字符串T/P中的第i个字符用T(i)来表示。 6.2 Z-box算法 [定义]Zi(S)表示在字符串S中从第i位起与S的前缀匹配的最长的字符串的长度。（数值） 注：如果S在上下文中很明显，Zi(S)可以用Zi来表示。 例：S=a a b c a a b x a a z 那么 1 2 3 4 5 6 7 8 Z5(S)=3； Z6=1；Z7= Z8=0 Z-box：其中每个与前缀匹配的子串就叫一个Z-box。对于任意数字i，如果S（i）属于某一个Z-box，则定义Li表示该Z-box的最左端的位置，Ri表示该Z-box的最右端的位置。 例：在上例中L6=5 R6=7 性质：if ij,then Ri=Rj [任务] 在线性时间内（O|S|）计算S的所有Zi [思想] Z2正常计算，然后归纳计算Zk，可以减少比较的次数 [思想]令S=P$T,其中$是特殊字符，在S和T中都不存在。利用Z算法计算Zi(S)。 [方案]对于任意j，如果Zn+1+j(S)=n,则P出现在T(j)处。 [加强]因为$的设定，对于任意i都有Zin,即k`总落在P内，所以当kn时（即在T中）Zk值不用计算，只需要维持（maintain）R和L的值。 6.3 BM算法 [名称] Boyer-Moore算法 [特点]从左向右移动，自右向左扫描 [技巧]坏字符规则 好后缀规则 6.3.1 坏字符规则 [实质]把P中的坏字符x移到T中的x的下面 [定义] 对于字母表中的每一个字符x，R(x)表示x在P中的最右端的位置，如果P中没有x，则R(x)=0。 [规则]对于P和T，如果P右面的n-i个字符都和T匹配，但是P(i) ≠T(k)。那么P可以向右移动max[1,i-R(T(k)]位。 1 2 3 4 5 6 7 8 9 0 [例] T= x p b c t b x a b p q x P= t p a b x a b 因为P(3)!=T(5),R(T(5))=R(t)=1 max[1,3- R(T(5))]=2 所以P可以向右移动2位，然后再从右向左依次同T比较 6.3.1 坏字符规则 普通坏字符规则有局限性： 1.不适合简单字母表 （DNA匹配） 2.不适合有大量重复子串的P （蛋白质匹配） 加强规则：当P(i) ≠T(k)时，如果T(k)=x，将P中位置i左面最近的x移到T(k)下面。（更好的体现了坏字符规则的精神）。 相关讨论：普通的坏字符规则节省空间，它只需要O|∑|（∑是字母表）的空间存放R(x)(R(x)是一个数组)；而加强坏字符规则可能需要更大的空间。 解决办法：可以不用二维数组，用一维数组，其中一维数组中的每个元素是一个数的序列。如：P=abacbabc 那么R(a)=6,3,1 所需空间O(n) 6.3.2 好后缀规则 坏字符规则的局限： 1.不适合小字母表 2.最差运行时间不是线性的 思想：看准T中的子串t，看P中还有没有子串匹配t 区别：坏字符规则是去匹配T中的一个坏字符；好后缀规则是去匹配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位。 例 1 2 3 4 5 6 7 8 9 0 1 2 3 4 T p r s t a b s t u b a b v q x r P q c a b d a b d a b 1 2 3 4 5 6 7 8 9 0 因为P(8)！=T(10)，t=ab，又因为t`在P中开始的位置是3，所以P向右移动6步 [对比]在本例中，坏字符规则只能使P向右移动1步 6.4 KMP算法 [名称] Knuth-Morris-Pratt算法 [特点]从左向右移动，从左向右比较 [定义]对于P中的每个位置i, spi(P)为P[1...i