算法導(dǎo)論-字符串匹配-劉凱宇

1、 字符串匹配字符串匹配2015.3.222015.3.22 劉凱宇劉凱宇大大 綱綱 字符串匹配問題定義字符串匹配問題定義 樸素算法樸素算法Rabin-KarpRabin-Karp算法算法有限自動(dòng)機(jī)算法有限自動(dòng)機(jī)算法KMPKMP算法算法2 2問題定義問題定義文本文本 T1n T1n 長(zhǎng)度長(zhǎng)度 n n模式模式 P1m P1m 長(zhǎng)度長(zhǎng)度 mmmmn n字母集字母集 =0,1 =0,1 =a,b,z =a,b,z 0sn-m, Ts+1.s+m = P1.m0sn-m, Ts+1.s+m = P1.m模式模式P P在文本在文本T T中出現(xiàn)，偏移為中出現(xiàn)，偏移為s s。文本文本 T Tb b c c a

2、 aa ab b a a a a b b c c a a b b a a c c模式模式 P Pa a b b a a a as = 3s = 33 3字符串匹配算法字符串匹配算法 樸素算法樸素算法Rabin-KarpRabin-Karp算法算法有限自動(dòng)機(jī)算法有限自動(dòng)機(jī)算法KMPKMP算法算法4 4樸素算法樸素算法模式模式 P1.mP1.m0sn-m, Ts+1.s+m = P1.m0sn-m, Ts+1.s+m = P1.m思想：思想： P1.mP1.m T1.nT1.n文本文本 T1.nT1.ns=0s=0s=1s=1s=n-ms=n-m5 5？文本文本 T = ababcabcacbab

3、T = ababcabcacbab模式模式 P = abcacP = abcacs = 0s = 0a ab ba ab bc ca ab bc ca ac cb ba ab ba ab bc ca ac ca ab bc ca ac cs = 1s = 1a ab bc ca ac cs = 2s = 2 s =3 s =3 a ab bc ca ac cs =4 s =4 a ab bc ca ac cs =5 s =5 a ab bc ca ac c T(n) = O(n-m+1)m) T(n) = O(n-m+1)m) 6 67 7字符串匹配算法字符串匹配算法 樸素算法樸素算法Rabi

4、n-KarpRabin-Karp算法算法有限自動(dòng)機(jī)算法有限自動(dòng)機(jī)算法KMPKMP算法算法7 7Rabin-KarpRabin-Karp算法算法字符串字符串3141531415 = 0,1,29 = 0,1,29十進(jìn)制數(shù)十進(jìn)制數(shù) 3141531415 映射映射數(shù)值數(shù)值t ts s模式模式 P1.mP1.m思想：思想： 文本子串文本子串 Ts+1.s+mTs+1.s+m 映射映射 數(shù)值數(shù)值p p0sn-m 0sn-m 有效偏移為有效偏移為s s Ts+1.s+m = P1.mTs+1.s+m = P1.mp =tp =ts s ？8 8 文本文本 T = 258569236589780T = 25

5、8569236589780 p = 2365p = 2365 模式模式 P P 2 23 36 65 5 tttttt 文本文本 T T 2 25 58 85 56 69 92 23 36 65 58 89 97 78 80 0 模式模式 P = 2365P = 2365 t t0 0 =2585 =2585 t t1 1 =5856 =5856 t t6 6 =2365 =2365 模式模式P P數(shù)值數(shù)值p p？ Ts+1.s+mTs+1.s+m數(shù)值數(shù)值t ts s？數(shù)值數(shù)值t ts+1s+1？ = 0,1,29 = 0,1,299 9運(yùn)用霍納法則運(yùn)用霍納法則t ts+1s+1= d(t=

6、d(ts s - d- dm-1m-1Ts+1) + Ts+m+1Ts+1) + Ts+m+1d = |d = | |p = Pm + d( Pm-1 + d( Pm-2 + d(P2 + dP1)p = Pm + d( Pm-1 + d( Pm-2 + d(P2 + dP1)t t0 0 = Tm + d(Tm-1 + d(Tm-2 + d(T2 + dT1) = Tm + d(Tm-1 + d(Tm-2 + d(T2 + dT1) 模式模式 P P 2 23 36 65 5 p = 5+10p = 5+10* *(6+10(6+10* *(3+10(3+10* *2)=2365 2)=23

7、65 文本文本 T T 2 25 58 85 56 69 92 23 36 65 58 89 97 78 80 0t t0 0=5+10=5+10* *(8+10(5+10(8+10(5+10* *2)=25852)=2585 =0,1,2,9 d = 10 =0,1,2,9 d = 10t t1 1= 10(t= 10(t0 0-10-103 3* *2)+6 =5856 2)+6 =5856 t t2 2= 10(t= 10(t1 1-10-103 3* *5)+9 =8569 5)+9 =8569 t t6 6= 10(t= 10(t5 5-10-103 3* *9)+5 =2365 9

8、)+5 =2365 預(yù)處理時(shí)間預(yù)處理時(shí)間O(m)O(m)1010 = Pm + d Pm-1 + d = Pm + d Pm-1 + d2 2Pm-2 + + dPm-2 + + dm-2m-2P2 + dP2 + dm-1 m-1 P1P1pp%q tpp%q ts s t ts s%q %q 問題：?jiǎn)栴}：p p和和t ts s的值可能太大的值可能太大方法：方法：p p和和t ts s的值取模的值取模q qt ts+1s+1 = ( d(t = ( d(ts s-Ts+1h)+Ts+m+1 )%q -Ts+1h)+Ts+m+1 )%q h= dh= dm-1 m-1 % q% q1111fo

9、r i=1 to mfor i=1 to mp = (dp+Pi)%qp = (dp+Pi)%qt ts+1s+1= d(t= d(ts s - d- dm-1m-1Ts+1) + Ts+m+1Ts+1) + Ts+m+1d = |d = | |取模運(yùn)算性質(zhì)取模運(yùn)算性質(zhì) (a + b)%c=(a%c+b%c)%c (a + b)%c=(a%c+b%c)%c (ab)%c=(a%c)(b%c)%c (ab)%c=(a%c)(b%c)%ct ts+1s+1=d(t=d(ts s - d- dm-1m-1Ts+1) + Ts+m+1Ts+1) + Ts+m+1 %q%q=( d(t=( d(ts s

10、-Ts+1h)+Ts+m+1 )%q -Ts+1h)+Ts+m+1 )%q (d(dm-1m-1%q)%q)= (d%q) (t= (d%q) (ts s%q - %q - (Ts+1%q)%q)%q%q + Ts+m+1%q %q(Ts+1%q)%q)%q%q + Ts+m+1%q %q1212若若t ts sp p Ts+1.s+mTs+1.s+m與模式與模式P P不匹配，偏移不匹配，偏移s s無效無效若若t ts s=p=pP P與與T T成功匹配成功匹配s s為有效偏移為有效偏移Ts+1.s+m = P1.mTs+1.s+m = P1.mTs+1.s+m P1.mTs+1.s+m P1

11、.mP P與與T T不匹配不匹配s s為偽命中點(diǎn)為偽命中點(diǎn)3 31 14 41 15 52 2q=13q=13t ts+1s+1= (31415-3= (31415-3* *10000)10000)* *10+2)%1310+2)%13 = (7-3 = (7-3* *3)3)* *10+2)%1310+2)%13 = 8 = 8 t ts s = 31415%13 = 31415%13 = 7 = 7 t ts+1s+1 = ( d(t = ( d(ts s-Ts+1h)+Ts+m+1 )%q -Ts+1h)+Ts+m+1 )%q h= dh= dm-1 m-1 % q% q文本文本T=23

12、59023141526739921T=2359023141526739921p=31415%13 = 7p=31415%13 = 7模式模式P=31415P=314152 23 35 59 90 02 23 31 14 41 15 52 26 67 73 39 99 92 21 18 89 93 311 11 0 01 17 78 84 45 51010 11 117 79 911 11偽命偽命中點(diǎn)中點(diǎn)合法合法匹配匹配匹配時(shí)間匹配時(shí)間T(n)=O(n-m+1)m)T(n)=O(n-m+1)m)實(shí)際應(yīng)用有效偏移少實(shí)際應(yīng)用有效偏移少 T(n)=O(n-m+1+cm)=O(n+m) T(n)=O(n

13、-m+1+cm)=O(n+m)t ts+1s+1 = (d(t = (d(ts s-Ts+1h)+Ts+m+1)%q -Ts+1h)+Ts+m+1)%q t t0 0 =23590%13=8 =23590%13=81313字符串匹配算法字符串匹配算法 樸素算法樸素算法Rabin-KarpRabin-Karp算法算法有限自動(dòng)機(jī)算法有限自動(dòng)機(jī)算法KMPKMP算法算法1414有限自動(dòng)機(jī)有限自動(dòng)機(jī)定義定義: :有限自動(dòng)機(jī)有限自動(dòng)機(jī)MM5 5元組元組(Q,q(Q,q0 0,A,A, ,) ) Q Q是狀態(tài)的有限集合是狀態(tài)的有限集合 q q0 0QQ是初始狀態(tài)是初始狀態(tài) A Q A Q是接受狀態(tài)集合是接受

14、狀態(tài)集合 是是MM的轉(zhuǎn)移函數(shù)的轉(zhuǎn)移函數(shù) 是有限輸入字母表是有限輸入字母表QQ QQP 1.mP 1.mQ=0,1,mQ=0,1,mq q0 0=0=0A = mA = m1 10 00 00 00 01 1狀態(tài)狀態(tài)輸入輸入a ba b=a,b=a,b(1,b)=0(1,b)=0 (0,a)=1(0,a)=11515思想：思想：構(gòu)造模式構(gòu)造模式P P的字符串匹配自動(dòng)機(jī)的字符串匹配自動(dòng)機(jī)逐個(gè)掃描文本逐個(gè)掃描文本T T中字符，記錄終止?fàn)顟B(tài)中字符，記錄終止?fàn)顟B(tài)狀態(tài)狀態(tài)q qA A時(shí)，得到一個(gè)匹配時(shí)，得到一個(gè)匹配1616構(gòu)造有限自動(dòng)機(jī)構(gòu)造有限自動(dòng)機(jī)a ab ba ac c模式模式P P前綴，后綴，真前綴

15、，真后綴前綴，后綴，真前綴，真后綴P P的前綴與的前綴與x x的后綴的最長(zhǎng)匹配長(zhǎng)度的后綴的最長(zhǎng)匹配長(zhǎng)度(ccaba)=3(ccaba)=3( ()=0)=0(ccab)=2(ccab)=2P P3 3=aba P=aba PP P4 4=abac P =abac P ac Pac P模式模式P P的后綴函數(shù)的后綴函數(shù) (x)=maxk: P(x)=maxk: Pk k x k0,m x k0,m1717構(gòu)造有限自動(dòng)機(jī)構(gòu)造有限自動(dòng)機(jī)字符串匹配自動(dòng)機(jī)字符串匹配自動(dòng)機(jī)模式模式P1.mP1.m狀態(tài)集合狀態(tài)集合Q=0,1,mQ=0,1,m初始狀態(tài)初始狀態(tài)q q0 0=0=0接受狀態(tài)接受狀態(tài)A=mA=m記

16、錄記錄P P的前綴與所讀入的前綴與所讀入T Ti i后綴的最長(zhǎng)匹后綴的最長(zhǎng)匹配長(zhǎng)度配長(zhǎng)度a ab ba ab ba ac ca a模式模式P P狀態(tài)狀態(tài)輸入輸入 a b c a b c 0 01 12 23 34 45 56 67 71 10 00 01 12 20 03 30 00 01 14 40 05 50 00 01 14 46 67 70 00 01 12 20 0q =0q =0(0,a) =(0,a) = (P(P0 0a)=a)=(a)=1(a)=1(0,b) =(0,b) = (P(P0 0b)=b)=(b)=0(b)=0(1,c) =(1,c) = (P(P1 1c)=c)

17、=(ac)=0(ac)=0q =1q =1(1,a) =(1,a) = (P(P1 1a)=a)=(aa)=1(aa)=1(1,b)=(1,b)= (P(P1 1b)=b)=(ab)=2(ab)=2(0,c) =(0,c) = (P(P0 0c)=c)=(c)=0(c)=0轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù)(q,a)=q(q,a)=q=(P(Pq qa)a)= maxk: P= maxk: Pk k P Pq qa a 1818a ab ba ab ba ac ca a模式模式P P輸入輸入 a b c a b c 狀態(tài)狀態(tài)0 01 12 23 34 45 56 67 71 10 00 01 12 20 03

18、30 00 01 14 40 05 50 00 01 14 46 67 70 00 01 12 20 0文本文本T Ta ab ba ab ba ab ba ac ca ab ba a0 01 12 23 34 45 54 45 56 67 72 23 3a a0 01 12 23 34 45 56 67 7a aa ab ba aa ab bc ca ab bb ba aa a匹配時(shí)間匹配時(shí)間T(n) = O(n)T(n) = O(n)1919計(jì)算轉(zhuǎn)移函數(shù)計(jì)算轉(zhuǎn)移函數(shù)預(yù)處理時(shí)間預(yù)處理時(shí)間T(n) =O(mT(n) =O(m3 3| |)|)compute-transition-functio

19、n(P,compute-transition-function(P,) )m=P.lengthm=P.lengthfor for q=0 to mq=0 to mforfor each charater a each charater ak=min(m+1,q+2)k=min(m+1,q+2)repeatrepeatk =k-1k =k-1untiluntil P Pk k P Pq qa a(q,a) = k(q,a) = kreturn return 2020字符串匹配算法字符串匹配算法 樸素算法樸素算法Rabin-KarpRabin-Karp算法算法有限自動(dòng)機(jī)算法有限自動(dòng)機(jī)算法KMPKM

20、P算法算法2121KMPKMP算法算法文本文本 T = ababcabcacbabT = ababcabcacbab模式模式 P = abcacP = abcac思想：思想：每一趟匹配出現(xiàn)每一趟匹配出現(xiàn)字符不等時(shí)，不字符不等時(shí)，不需回溯需回溯利用已得到的部利用已得到的部分匹配的結(jié)果將分匹配的結(jié)果將模式向右滑動(dòng)盡模式向右滑動(dòng)盡可能遠(yuǎn)的距離，可能遠(yuǎn)的距離，繼續(xù)進(jìn)行比較。繼續(xù)進(jìn)行比較。a ab bc ca ac ca ab ba ab bc ca ab bc ca ac cb ba ab b文本文本T T模式模式P P2222文本文本T Tb ba ac cb ba ab ba ab ba aa a

21、b bc cb ba as= 4s= 4a ab ba ab ba ac ca a模式模式P Ps s= 6= 6a ab ba ab ba ac ca aa ab ba ab ba aP P5 5a ab ba aP P3 3next5=3next5=3s s=s+(5-next5)=s+(5-next5)s s= s +(q-nextq)= s +(q-nextq)2323P Pq q的真后綴與的真后綴與P P的前綴最長(zhǎng)匹配長(zhǎng)度的前綴最長(zhǎng)匹配長(zhǎng)度nextq=maxk:kqnextq=maxk:kq且且P Pk k P Pq q P Pq q的真后綴與的真后綴與P P的前綴最長(zhǎng)匹配長(zhǎng)度的前綴最長(zhǎng)匹配長(zhǎng)度a ab ba ab ba ac ca anext1=0next1=0next2=0next2=0a ab ba ab ba ac ca aa ab ba ab ba ac ca anext3=1next3=1a ab ba ab ba ac ca aa ab ba ab ba ac ca aa ab ba ab ba ac ca aa ab ba ab ba ac ca anext4=2next4=2next5=3next5=3next6=0next6=0next7=1next7=1a ab ba ab ba ac ca aa ab ba ab ba ac ca aa ab b