|
KMP算法与一个经典概率问题2009-12-09 09:35 考虑一个事件，它有两种概率均等的结果。比如掷硬币，出现正面和反面的机会是相等的。现在我们希望知道，如果我不断抛掷硬币，需要多长时间才能得到一个特定的序列。
序列一：反面、正面、反面
序列二：反面、正面、正面 首先，我反复抛掷硬币，直到最近的三次抛掷结果形成序列一，然后我记下这次我抛掷了多少次才得到了我要的序列。重复执行这个过程，我可以算出得到序列一平均需要的抛掷次数。同样地，反复抛掷硬币直到序列二产生，它所需要的次数也有一个平均值。你认为这两个平均值哪一个大哪一个小？换句话说，出现序列一平均所需的抛掷次数少还是出现序列二平均需要的次数少？
大多数人会认为，两个序列会以同样快的速度出现，因为在所有“正”和“反”的8种三元组合里，“反正反”和“反正正”各占1/8，其概率是均等的。而事实上，我们将会看到掷出序列二所需的次数更少一些。不妨考虑这样一个问题：在由“正”和“反”构成的n位01序列中，有多少个序列以序列一结尾但之前不曾出现过序列一？有多少个序列以序列二结尾但之前不曾出现过序列二？当n比较小时，两者答案是一样的（例如n=3时符合要求的情况都是唯一的），但到后来n越大时，两者的差距越明显：后者的个数总比前者的个数要多一些。不妨看一看n=6的情况。对于序列一，只有以下5个序列是符合要求的： 反反反反正反 反正正反正反
正正正反正反
正反反反正反
正正反反正反
但对于序列二来说，符合条件的序列就有7个：
反反反反正正 反正反反正正
反反正反正正
正反反反正正
正正反反正正
正正正反正正
正反正反正正
你可以通过计算机编程枚举，计算一下n为其它值的情况。计算结果和刚才也一样：在n位01序列中，以序列二结尾但之前不含序列二的情况不会少于以序列一结尾但之前不含序列一的情况。这说明，抛掷第n次硬币后恰好出现了序列二，其概率不会小于恰好出现序列一的概率。显然，当n渐渐增大时，这个概率应该呈下降趋势；同时，随着n的增长，两个序列各自出现的概率由相等开始慢慢拉开差距，第n次抛掷产生序列二的概率下降得要缓慢一些，或者说更多的情况集中发生在n更小的时候。因此总的来说，出现序列二所需要的抛掷硬币次数的期望值更小。
虽然我们通过一系列的观察验证了这个结论，并且我们也相信这个结论是正确的（虽然没有严格的证明），但我们仍然不是很接受这个结论。这种情况是有悖于我们的直觉的，它与我们的生活经验不相符合。此刻，我们迫切需要一个解释，来说明这种出人意料的反常现象产生的原因。 如果不亲自做几次试验的话，你很难体会到这种微妙的差距。考虑整个游戏的实际过程，“反正正”序列显然会出现得更早一些。假如某一次我们得到了序列“反正”。如果我们需要的是“反正反”序列，那么下一次抛掷结果为反面将结束本轮的抛掷，而下一次是正面则前功尽弃，你必须再次从零开始。如果我们需要的是“反正正”序列，那么下一次抛掷结果为正面将结束本轮的抛掷，而下一次是反面的话我至少不会惨到一切归零，这相当于我已经有了一个反面作为新的开头，只需再来两个正面即可。这样看的话，提前掷出“反正正”的可能性更大一些。 反复体会上面的想法，了解KMP算法的网友会恍然大悟：这就是KMP算法的基本思路！考虑这样一个问题：我们在当前字串中寻找子串“反正正”第一次出现的位置。假如当前已经能匹配模式串的前两个字“反正”，主串中的下一个字是“正”则匹配成功，主串的下一个字是“反”则将使模式串的当前匹配位置退到第一个字。考虑一个更复杂的例子：我们希望在主串中寻找子串abbaba，现在已经在主串中找到了abbab。如果主串下一个字符是a，则成功匹配；如果主串下一个字符是b，则模式串最多能匹配到的位置退到了第三个字符，我只需要从abb开始继续匹配，而不必一切从头再来。 我们可以用KMP算法完美地解决上面的问题。首先预处理出一个数组c，c[i,0]表示模式串匹配到了第i个字符，主串下一个字符为0（反）时，模式串的匹配位置将退到哪里；同样地，c[i,1]表示模式串匹配到了第i个字符，主串下一个字符为1（正）时，新的模式串匹配位置在什么地方。设f[i,j]表示第i次抛掷硬币后恰好匹配到模式串第j位有多少种情况，则f[i,j]=Σf(i-1,k) + Σf(i-1,l)，其中k满足c[k,0]=j，l满足c[l,1]=j。将f[i,j]除以2的i次方，我们就得到了相应的概率值。或者更直接地，设P[i,j]表示第i次抛掷硬币后，最远能匹配到的模式串位置是第j位的概率，则P[i,j]=Σ( P(i-1,k)/2 ) + Σ( P(i-1,l)/2 )。注意，我们还应该添加一种特殊的概率值P[i,*]，它表示在主串第i个字符以前已经成功匹配过的概率，这样的话下表中每一列的和才能为1。 来看一看程序的输出结果：
Pattern 1: s[]="aba" 主串位置 1 2 3 4 5 6 7 8 9 10 匹配到s[0] 0.5000 0.2500 0.2500 0.2500 0.2188 0.1875 0.1641 0.1445 0.1270 0.1113 匹配到s[1] 0.5000 0.5000 0.3750 0.3125 0.2813 0.2500 0.2188 0.1914 0.1680 0.1475 匹配到s[2] 0.0000 0.2500 0.2500 0.1875 0.1563 0.1406 0.1250 0.1094 0.0957 0.0840 匹配到s[3] 0.0000 0.0000 0.1250 0.1250 0.0938 0.0781 0.0703 0.0625 0.0547 0.0479 已找到匹配 0.0000 0.0000 0.0000 0.1250 0.2500 0.3438 0.4219 0.4922 0.5547 0.6094 Pattern 2: s[]="abb"
主串位置 1 2 3 4 5 6 7 8 9 10 匹配到s[0] 0.5000 0.2500 0.1250 0.0625 0.0313 0.0156 0.0078 0.0039 0.0020 0.0010 匹配到s[1] 0.5000 0.5000 0.5000 0.4375 0.3750 0.3125 0.2578 0.2109 0.1719 0.1396 匹配到s[2] 0.0000 0.2500 0.2500 0.2500 0.2188 0.1875 0.1563 0.1289 0.1055 0.0859 匹配到s[3] 0.0000 0.0000 0.1250 0.1250 0.1250 0.1094 0.0938 0.0781 0.0645 0.0527 已找到匹配 0.0000 0.0000 0.0000 0.1250 0.2500 0.3750 0.4844 0.5781 0.6563 0.7207 这下我们可以清楚地看到，序列二提前出现的概率要大得多。注意到，根据我们的概率定义，表格中每一列的数字之和都是1。同时，倒数第二行的数字之和（有无穷多项）也应该为1，因为最后一行的概率就是倒数第二行的概率值累加的结果，而根据最后一行概率的定义，主串无穷长时已找到匹配的概率应该为1。因此，我们也可以把倒数第二行看作是模式串在主串第i个位置首次匹配成功的概率。我们可以根据这一结果近似地计算出抛掷次数的期望值。
kmp算法是一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是根据给定的模式串W1,m,定义一个next函数。next函数包含了模式串本身局部匹配的信息。
目录
kmp算法-学习介绍
详细算法：一般的KMP算法 KMP算法的优化 基本思想 BM算法 基本思想kmp算法-学习介绍 详细算法： 一般的KMP算法 KMP算法的优化 基本思想 BM算法 基本思想 展开 编辑本段kmp算法-学习介绍 完全掌握KMP算法思想 学过数据结构的人，都对KMP算法印象颇深。尤其是新手，更是难以理解其涵义，搞得一头雾水。今天我们就来面对它，不将它彻底搞懂，誓不罢休。 如今，大伙基本上都用严蔚敏老师的书，那我就以此来讲解KMP算法。 严老的《数据结构》79-84页讲了基本的匹配方法，这是基础。先把这个搞懂了。 80页在讲KMP算法的开始先举了个例子，让我们对KMP的基本思想有了最初的认识。目的在于指出“由此，在整个匹配的过程中，i指针没有回溯，”。 在此也推荐张铭、赵海燕、王腾蛟编著的《数据结构与算法》一书（北京大学出版社），里面的“字符串”一章对KMP算法有较为详尽易懂的介绍。 编辑本段详细算法： 一般的KMP算法 现在讨论一般情况。 假设 主串：s: ‘s(1) s(2) s(3) ……s(n)’ ; 模式串 ：p: ‘p(1) p(2) p(3)…..p(m)’ 把课本上的这一段看完后，继续 现在我们假设 主串第i个字符与模式串的第j(j<=m)个字符‘失配’后，主串第i个字符与模式串的第k(k<j)个字符继续比较 此时，s(i)≠p(j), 有 主串： S(1)…… s(i-j+1)…… s(i-1) s(i) …………. || (相配) || ≠(失配) 匹配串： P(1) ........... p(j-1) p(j) 由此，我们得到关系式 ‘p(1) p(2) p(3)…..p(j-1)’ = ’ s(i-j+1)……s(i-1)’ 由于s(i)≠p(j)，接下来s(i)将与p(k)继续比较，则模式串中的前(k-1)个字符的子串必须满足下列关系式，并且不可能存在 k’>k 满足下列关系式：(k<j), ‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(i-k+1)s(i-k+2)……s(i-1)’ 即： 主串： S(1)……s(i-k +1) s(i-k +2) ……s(i-1) s(i) …………. || (相配) || || ?(有待比较) 匹配串： P(1) p(2) ……..... p(k-1) p(k) 现在我们把前面总结的关系综合一下 有： S(1)…s(i-j +1)… s(i-k +1) s(i-k +2) …… s(i-1) s(i) …… || (相配) || || || ≠(失配) P(1) ……p(j-k+1) p(j-k+2) …...... p(j-1) p(j) || (相配) || || ?(有待比较) P(1) p(2) ……...... p(k-1) p(k) 由上，我们得到关系： 'p(1) p(2) p(3)…..p(k-1)’ = ' p(j-k+1)p(j-k+2)……p(j-1)’ 接下来看“反之，若模式串中存在满足式(4-4)。。。。。。。”这一段。看完这一段，如果下面的看不懂就不要看了。直接去看那个next函数的源程序。(伪代码) K 是和next有关系的，不过在最初看的时候，你不要太追究k到底是多少，至于next值是怎么求出来的，我教你怎么学会。 课本83页不是有个例子吗？就是 图4.6 你照着源程序，看着那个例子慢慢的推出它来。看看你做的是不是和课本上正确的next值一样。 在理解上面代码的基础上，建议自己寻找一些KMP算法的练习，也可以自己写两个较为简单的字符串进行人脑模拟这种方法的练习，以加深对算法的理解。 KMP算法的优化 KMP算法是可以被进一步优化的。 我们以一个例子来说明。譬如我们给的P字符串是“abcdaabcab”，经过KMP算法，应当得到“特征向量”如下表所示： 下标i 0 1 2 3 4 5 6 7 8 9 p(i) a b c d a a b c a b next[i] -1 0 0 0 0 1 1 2 3 1 但是，如果此时发现p(i) == p(k)，那么应当将相应的next[i]的值更改为next[k]的值。经过优化后可以得到下面的表格： 下标i 0 1 2 3 4 5 6 7 8 9 p(i) a b c d a a b c a b next[i] -1 0 0 0 0 1 1 2 3 1 优化的next[i] -1 0 0 0 -1 1 0 0 3 0 附： KMP算法查找串S中含串P的个数count #include <iostream> #include <stdlib.h> #include <vector> using namespace std; inline void NEXT(const string& T,vector<int>& next) { //按模式串生成vector,next(T.size()) next[0]=-1; for(int i=1;i<T.size();i++ ){ int j=next[i-1]; while(T[i]!=T[j+1]&& j>=0 ) j=next[j] ; //递推计算 if(T[i]==T[j+1])next[i]=j+1; else next[i]=0; // } } inline string::size_type COUNT_KMP(const string& S, const string& T) { //利用模式串T的next函数求T在主串S中的个数count的KMP算法 //其中T非空， vector<int> next(T.size()); NEXT(T,next); string::size_type index,count=0; for(index=0;index<S.size();++index){ int pos=0; string::size_type iter=index; while(pos<T.size() && iter<S.size()){ if(S[iter]==T[pos]){ ++iter;++pos; } else{ if(pos==0)++iter; else pos=next[pos-1]+1; } }//while end if(pos==T.size()&&(iter-index)==T.size())++count; } //for end return count; } int main(int argc, char *argv[]) { string S="abaabcacabaabcacabaabcacabaabcacabaabcac"; string T="ab"; string::size_type count=COUNT_KMP(S,T); cout<<count<<endl; system("PAUSE"); return 0; } 补上个Pascal的KMP算法源码 PROGRAM Impl_KMP; USES CRT; CONST MAX_STRLEN = 255; VAR next : array [ 1 .. MAX_STRLEN ] of integer; str_s, str_t : string; int_i : integer; Procedure get_nexst( t : string ); Var j, k : integer; Begin j := 1; k := 0; while j < Length(t) do begin if ( k = 0 ) or ( t[j] = t[k] ) then begin j := j + 1; k := k + 1; next[j] := k; end else k := next[k]; end; End; Function index( s : string; t : string ) : integer; Var i, j : integer; Begin get_next(t); index := 0; i := 1; j := 1; while ( i <= Length(s) ) and ( j <= Length(t) ) do begin if ( j = 0 ) or ( s[i]= t[j] ) then begin i := i + 1; j := j + 1; end else j := next[j]; if j > Length(t) then index := i - Length(t); end; End; BEGIN ClrScr;{清屏，可不要} Write(‘s = ’); Readln(str_s); Write(‘t = ’); Readln(str_t); int_i := index( str_s, str_t ); if int_i <> 0 then begin Writeln( 'Found' , str_t,' in ', str_s, 'at ', int_i,' .' ); end else Writeln( 'Cannot find ', str_t,' in' , str_s, '. '); END. index函数用于模式匹配，t是模式串，s是原串。返回模式串的位置，找不到则返回0 编辑本段基本思想 假设在模式匹配的进程中，执行T[i]和W[j]的匹配检查。若T[i]=W[j]，则继续检查T[i+1]和W[j+1]是否匹配。若T[i]<>W[j]，则分成两种情况：若j=1，则模式串右移一位，检查T[i+1]和W[1]是否匹配；若1<j<=m，则模式串右移j-next(j)位，检查T[i]和W[next(j)]是否匹配。重复此过程直到j=m或i=n结束。 文献中，朱洪对KMP算法作了修改，他修改了KMP算法中的next函数，即求next函数时不但要求W[1,next(j)-1]=W[j-(next(j)-1),j-1]，而且要求W[next(j)]<>W[j]，他记修改后的next函数为newnext。显然在模式串字符重复高的情况下,朱洪的KMP算法比KMP算法更加有效。 以下给出朱洪的改进KMP算法和next函数和newnext函数的计算算法。 算法1.1：KMP串匹配算法 输入: 正文串j和模式串W[1,m] 输出: 匹配结果match[1,n] procedure KMP begin i=1 j=1 while i<=n do while j<>0 and W[j]<>T[i] do j=newnext[j] endwhile if j=m return “success” else j++ i++ endif endwhile return “failure” end 算法1.2: next函数和newnext函数的计算算法 输入: 模式串W[1,m] 输出: next[1,m+1]和newnext[1,m] function NEXT begin next[1]=newnext[1]=0 j=2 while j<=m do i=next[j-1] while i<>0 and W[i]<>W[j-1]) do i=next[i] endwhile next[j]=i+1 j=j+1 endwhile end function NEWNEXT begin newnext(1)=0 j=2 while j<=m do i=next(j) if i=0 or W[j]<>W[i+1] newnext[j]=i else newnext[j]=newnext[i] endif j++ endwhile end 朱洪证明了算法1的时间复杂度为O(n)，算法2的时间复杂度为O(m)。 下面是更加简洁的算法： void GetNext(char T[ ],int next[ ]) { next[1]=0; j=1;k=0; while(j<T[0]) if ((k==0)||(T[j]==T[k]) { j++; k++; next[j]=k; } else k=next[k]; } 编辑本段BM算法 BM算法和KMP算法的差别是对模式串的扫描方式自左至右变成自右至左。另一个差别是考虑正文中可能出现的字符在模式中的位置。这样做的好处是当正文中出现模式中没有的字符时就可以将模式大幅度滑过正文。 BM算法的关键是根据给定的模式W[1,m],，定义一个函数d: x->{1,2,…,m} ,这里x∈∑。函数d给出了正文中可能出现的字符在模式中的位置。 函数d的定义如下：对每个x∈∑ 编辑本段基本思想 假设在执行正文中自位置i起“返前”的一段与模式的自右至左的匹配检查中，一旦发现不匹配(不管在什么位置)，则去执行由Wm与ti+d(x)起始的自右至左的匹配检查，这里x是字符t。。它的效果相当于把模式向右滑过d(ti)一段距离。显然,若ti不在模式中出现或仅仅在模式末端出现，则模式向右滑过的最大的一段距离m。图1.1示出了执行BM算法时的各种情况。实线连接发现不匹配以后要进行比较的正文和模式中的字母，虚线连接BM算法在模式向右滑后正文和模式中应对齐的字母，星号表示正文中的一个字母。 图1.1：执行BM算法时的各种情况 BM算法由算法1.3给出，函数d的算法由算法1.4给出。计算函数d的时耗显然是Θ(m)。BM算法的最坏情况时耗是Θ(mn)。但由于在实用中这种情况极少出现，因此BM算法仍广泛使用。 算法1.3：BM串匹配算法 输入: 正文串W[1,m]和模式串T[1,n] 输出: 匹配结果match[1,n] procedure BM begin i=m Repeat j=m k=i while(j>0)and(w[j]=t[k]) do j=j-1 k=k-1 endwhile i=i+d[t[i]] Until (j=0)or(i>n) If j=0 return “SUCCESS” else return “FAILURE” endif end 算法1.4: d函数计算法: function d:integer; begin for x∈∑ do d(x)=m for j=m-1 downto 1 do if d(w[j])=m d(w[j]):=m-j endfor end xi+1=ord(ti+1)dm-1+ord(ti+2)dm-2+…+ord(ti+m) =(xi-ord(ti)dm-1).d+ord(ti+m) 因此有 h(xi+1)=((h(xi)-x·ord(ti))·d+ord(ti+m)mod q ，i=1,2,……,n-m 这里x是一常数，x=dm-1mod q。 这就是计算每一长度为m的字符段的散列函数值的递推公式。RK串匹配算法由算法1.5给出。 算法1.5：RK串匹配算法 program RK; begin {计算x,x:=d↑(m-1) mod q} x=1 for i=1 to m-1 do x=(32*x)mod q {计算模式W的散列函数值} s=0 for i=1 to m do s=((s*32)+ord(w[i])) mod q {计算正文T的第一个长度为m的字符段的散列函数值} t=0 for i=1 to m do t=(t*32+ord(w[i])) mod q {如果正文的第一个长度为m的字符段和模式有相同的散列函数值,则进行匹配检查.否则,以及在匹配检查失败情况下,继续计算下一个字符段的散列函数值} i=1 while i<=n-m do if s=t {进行匹配检查} k=1 j=i while (t[j]=w[k]) and (k<=m) do j=j+1 k=k+1 endwhile if i<n-m {计算下一字符段的散列函数值} t=((t-x*ord(t[i]))*32+ord(t[i+m])) mod q i=i+1 endif endif endwhile return “FAILURE” end 显然,如果不计执行匹配检查的时间，则RK算法的剩余部分执行时间是Θ(m+n)。不过，如果计及执行匹配检查的时间,则在理论上,RK算法需要时耗Θ(mn)。但是,我们总可设法取q适当大，使得mod函数在计算机中仍可执行而冲突(即不同的字符串具有相同的散列值)又极小可能发生，而使算法的实际执行时间只需Θ(m+n)。 |
|
|
