大家好! 数据结构与算法,这一讲的内容是第四章字符串,其中的 快速模式匹配方法KMP算法。 那在快速匹配算法里面呢, 我们最主要的就是说,尽量的不要回溯。 KMP算法它实际上是一种无回溯的匹配方法。 一旦发生不等的时候, 那我们怎么样用P里面的哪一个字符pk和ti继续进行比较? Knuth等人呢, 发现这个k值,仅仅依赖于模式本身, 而跟目标无关。那我们来研究一下,这个匹配的过程。 对于这样的一个目标串,还有模式串, 他们前面的比较是哦,逐一相等的, 但是呢,在ti和pj位不等。那如果是 朴素的匹配, 就会回到 ti-j+1这一位跟 p0继续比, 这样的一个匹配过程。 如果我们事先知道, 这个字串和这个字串,它不等。 这实际上 是首和尾的真字串。那就是说我们发生不等的时候 盖住它。然后呢,看这个P, 模式,它的首尾的这个真字串。 它如果是说不等的话呢,我们下一趟比较就是没有意义的。 因为在很快就会发生不等。 那继续往下头看。哦,还有这样的一个 字串, 就是我们这个串长呢,它是哦,缩短了一个。 哦,但是呢,其实我们的右滑呢,其实是往右面滑两位了。 那如果是说它对应的也还是不等,那它也没有必要继续比。 直到有那么一个k值, 这个k值呢,它是首尾串的这个真字串的长度。 使得我们前面的这个哦,首串的 k位和尾串的k位呢,它是 对应相等的。对于这样的一个 情况,那既然是前面这个k位对应相等, 因为 p的这个尾串,它刚才 已经跟目标串进行过比较。那么我们就可以知道, 相应的p0跟这个ti-k, 还有pk-1 到ti-1,它们也是对应相等的。因此呢,就只须要 拿pk和ti来继续比较。 整个这个模式,它就可以右滑借减k位, 那来观察一下,字符串的特征向量。 那这个特征向量呢,它其实是哦, 一组 整数值。那也有些文献呢,把它叫做next数组。 那我们来看它的这个构造方法。那其实呢,就是 要寻找递接着位置它前面的 首尾真字串的,配串里面的最长的 另一个。 然后对其它的有些特殊情况,像j=0的时候,我们规定它等于-1. 那这个是为了算法的方便。 啊,如果是说不存在这样的首尾的真字串呢,那就是哦, 它的k值就是0。我们来看为什么我们要找最长的哪一个? 下面是它的特征值。那这个特征值里面呢,本来在 N=4这移位可以看到前面它的这个首尾的真字串呢,实际上是 等于3。 那现在我们让它等于1。啊,等于1它也是对的。因为它是 就是说有这样的程度为1的首尾配串。 哦,但是呢,如果不是取得这个最大值3, 那在某些情况我们就会哦,错过一些匹配。 例如我们在匹配到这一次的时候, 那P4哦, 发生不等的时候,我们可以看到。 因为我这里给的这个k值不是这个最大的那一个,而是给的1。 那我就会拿着P1来跟这个, 目标串里面的这个下标7, 来比较。 那因此呢,它是一个非常大的一个滑动。就是j减这个 k,所以是哦, 这个j是等于4,然后k=1,那就滑动3位。 那其实本来那是4-3,只能滑动1位。所以它就是错过了一个可能的 比较。好,那我们来看一下这个KMP模式匹配 的这么一个过程。对于这个模式我们求出了这个 特征向量。那我们根据这个特征向量值,哦,当 某一为发生不等的时候,直接查这个特征向量表。 然后拿出这个相应的这个哦,k值来。然后呢,就是 说这个Pk呢,直接跟刚才的这个哦,Ti进行比较。 噢,这个匹配的过程就完成了。它是非常迅速的。那我们看, KMP模式匹配算法。 那这个算法呢,哦,我们假设它已经给了这样的一个特征向量, 然后呢,是从模式的第0位和 目标的指定的start位开始。 那这个算法我们就是哦, 从这个ij这两个下标指向呢, 往后面走。那如果是说相应的位子是相等的,那么就是哦, i++, j++就是继续下一位的逐位比较。 那如果是说在某一位 发现是j==-1了,实际上是碰到了 这个next是0的情况,那就是说在这一位发生 不等。应该是把j+1,然后这个哦, 等于0,然后呢,i呢,也加一。 也就是说,目标呢,是换一个位子继续比较。 它也是没有回溯的。如果是说发生了不等的情况,那么我们这个j呢,就是 用特征向量里面的next j,也就是那个k值。 啊,这个k值一定是小于j值的。啊,这个 P, j, 跟T, i 继续进行 比较。完成这个循环以后,如果这个j,它是 大于等于模式串的长度的,那表示匹配是成功的。 否则呢,就是匹配失败。 对应的求特征向量的算法呢, 它是一个递归的这个过程。对于n0的情况呢,我们是 归定啊,它等于-1。然后假设 对于前面的若干位,也就是说j之前的这个位, 我们都求出来了。假设我们是nj呢,它就等于k. 那现在我们要求n j+1, 那如果是说, 现在这个pj,它不等于pk, 那这个时候呢,直接令k呢,等于nk.那就是发生不等的时候, 我们用它前面的那一个哦,特征来继续匹配。那 所以这里其实可以看出它也是一个KMP的一个过程。就是前面是自己求出来,自己一个 子的特征向量,然后用这个子特征向量用来做这个匹配的过程。 好,一直到条件um, 不满足,也就是说一直到pj等于pk,这样的情况。 那这个时候呢,nj+1呢,它等于k+1. 这样就是说这个特征 的向量,它的那个首尾串,这个字串呢,它长度是加1的。 特征向量的一个算法就可以看出,首先对这些特殊的情况进行一下处理。 对于j=1的情况呢,其实也是可以用这个循环来,来求出来的。对于j=1, 它的特征向量值呢,其实就是等于0,因为哦,前面的 没有真的这个值串。 好!对于一个借它求出来的这样的一个值,这样的情况, k值呢,是一致的。那如果是, 当前这个哦,P[j], 它不等于P[k]呢,我们就直接拿这个前面得到的 这个k的这个特征值来, 附给我们现在的这个k, 就是k = next[k]. 这个肯定是要变小的。因为哦, k是小于next[k]的。j也是小于next[j]的。 啊,如果是相等的情况,那就是说j++, k++, 那往下面继续比。um,所谓配串长了是加了1。 而且呢,我们让这个next[j]它的值呢,是等于k。 这个实际上是已经加过1 的那个k。 哦,这是求 特征向量的一个演示。那我们可以看到呢,在求的过程中, 它都是要遮着自己,然后看前面的这个串的首尾真字串。 而且这些特征值,它的这些变化的过程呢,它都是渐变的,也就是顶多是加1加1 这样的变。当然如果是降,它是可以直接降到0, 或者是降到一个比这个3,比这个当前这个k 值小一些的, 这个数。那我们看到它这个首尾串的匹配的过程。 那这个算法它有没有右滑的余地呢?就是说 我们来看一下,如果是说Pj==Pk的情况会怎么样? 因为Pj==Pk而刚才呢,是 Pj,它不等于ti. 因此可以想像得到,你下一次用Pk 来跟ti来比,他其实是肯定不等的。因此这个是 可以哦,掠过去。那这个不等的这个情况呢,我们可以直接的记录在特征数组里头。 那我们来看这个例子。啊,这个例子里面呢,就是哦,相应的这个哦, 特征向量已经计算出来。当它P的3, 这一位发生 不等的时候,那么根据特征向量值呢, 它是用啊,这个K呢,等于0来比,也就是说P[0], 这个,因为P[0],它也是a, 它就等于这个P[3]. 那显然你刚才这里不等,它也是不会再相等的。所以这一行标红色的,它实际上是 冗余的一次比较。因此呢,可以做一些优化。这个优化呢,其实就是在这个地方, 也就是说如果是um, P[k]==P[j]的话呢,我们让它的这个next直接呢, 直接等于next[k]. 因为j是大于k的,所以呢,它这样 的优化呢,它肯定是得到一个更小的这个k值。 那我们看这个next数组,哦,非优化版和优化版,它的差异。 啊,那其实呢哦,可以看首先是求出这样的, 每一个特征位,它的首尾字串的,这样的哦,这程的k. 然后呢,我们的优化主要就是看它是不是 Pk==Pj? 如果等的话,我就直接让这个next[j]=next[k], 噢, 就做了这些优化。总体来说,这个哦,优化以后的这个next数组的 哦,特征值,它是比优化之前的那些呢,它有一些位是要小一些的。 那KMP算法的时间效率呢, 哦,我们虽然说看起来它像是一个双重循环, 但是呢, 在循环体里面,最重要的j=Next[j]这个语句, 它的执行的总次数是不能够超过n次的。 因为每一次执行都会使得j要减少至少1。 那对于j的增加的操作呢,只有j++这一次。 因此,如果是说j = N[j], 它的总的执行超出过n次的话,它必然会使得 j这个值呢,是会比-1 小很多。但是在整个算法里面, 其实只是在偶然的情况j变成-1,但是马上就加回到0。 因为这是哦,算法的一个处理的技巧。 因此呢,整个这个执行的过程呢,就是 哦,倒n的,也就是KMP算法整个过程是到n的。 那对于这个特征向量的一个预处理过程,它实际上也是一个KMP的这样的一个过程。 因此,它的总的时间呢,是到m的。所以它加起来是到达 n+m的。 那我们总结一下,单模式匹配算法它的的时间效率。 那我们主要说一下,朴素的和 KMP算法。那朴素算法它不需要预处理,但它的, 模式匹配时间是到达n乘m. 对于这个KMP算法呢,它是有预处理时间的,它预处理只须要到达m,哦, 然后它的这个哦, 整个匹配呢,是到达n. 当然因为这里其实是 哦,一个缺界,所以它们其实都可以用theta来表示的。 感兴趣的同学可以去研究一下,其它的快速的模式匹配算法。 最后哦,留给大家这个思考。 在这个特征向量的求值中呢,其实有不同的规定。啊,就是有不同的这些方法。 那么这些不同的方法呢,它其实适合于一些不同的应用。 哦,我们可以去哦,比较一下一些而且实现它。 谢谢大家!