算法导论-字符串匹配-刘凯宇

1、 字符串匹配字符串匹配2015.3.222015.3.22 刘凯宇刘凯宇大大 纲纲 字符串匹配问题定义字符串匹配问题定义 朴素算法朴素算法Rabin-KarpRabin-Karp算法算法有限自动机算法有限自动机算法KMPKMP算法算法2 2问题定义问题定义文本文本 T1n T1n 长度长度 n n模式模式 P1m P1m 长度长度 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中出现，偏移为中出现，偏移为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算法算法有限自动机算法有限自动机算法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算法算法有限自动机算法有限自动机算法KMPKMP算法算法7 7Rabin-KarpRabin-Karp算法算法字符串字符串3141531415 = 0,1,29 = 0,1,29十进制数十进制数 3141531415 映射映射数值数值t ts s模式模式 P1.mP1.m思想：思想： 文本子串文本子串 Ts+1.s+mTs+1.s+m 映射映射 数值数值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数值数值p p？ Ts+1.s+mTs+1.s+m数值数值t ts s？数值数值t ts+1s+1？ = 0,1,29 = 0,1,299 9运用霍纳法则运用霍纳法则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 预处理时间预处理时间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 问题：问题：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 = | |取模运算性质取模运算性质 (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为伪命中点为伪命中点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伪命伪命中点中点合法合法匹配匹配匹配时间匹配时间T(n)=O(n-m+1)m)T(n)=O(n-m+1)m)实际应用有效偏移少实际应用有效偏移少 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算法算法有限自动机算法有限自动机算法KMPKMP算法算法1414有限自动机有限自动机定义定义: :有限自动机有限自动机MM5 5元组元组(Q,q(Q,q0 0,A,A, ,) ) Q Q是状态的有限集合是状态的有限集合 q q0 0QQ是初始状态是初始状态 A Q A Q是接受状态集合是接受

14、状态集合 是是MM的转移函数的转移函数 是有限输入字母表是有限输入字母表QQ QQP 1.mP 1.mQ=0,1,mQ=0,1,mq q0 0=0=0A = mA = m1 10 00 00 00 01 1状态状态输入输入a ba b=a,b=a,b(1,b)=0(1,b)=0 (0,a)=1(0,a)=11515思想：思想：构造模式构造模式P P的字符串匹配自动机的字符串匹配自动机逐个扫描文本逐个扫描文本T T中字符，记录终止状态中字符，记录终止状态状态状态q qA A时，得到一个匹配时，得到一个匹配1616构造有限自动机构造有限自动机a ab ba ac c模式模式P P前缀，后缀，真前缀

15、，真后缀前缀，后缀，真前缀，真后缀P P的前缀与的前缀与x x的后缀的最长匹配长度的后缀的最长匹配长度(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的后缀函数的后缀函数 (x)=maxk: P(x)=maxk: Pk k x k0,m x k0,m1717构造有限自动机构造有限自动机字符串匹配自动机字符串匹配自动机模式模式P1.mP1.m状态集合状态集合Q=0,1,mQ=0,1,m初始状态初始状态q q0 0=0=0接受状态接受状态A=mA=m记

16、录记录P P的前缀与所读入的前缀与所读入T Ti i后缀的最长匹后缀的最长匹配长度配长度a ab ba ab ba ac ca a模式模式P P状态状态输入输入 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转移函数转移函数(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 状态状态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匹配时间匹配时间T(n) = O(n)T(n) = O(n)1919计算转移函数计算转移函数预处理时间预处理时间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算法算法有限自动机算法有限自动机算法KMPKM

20、P算法算法2121KMPKMP算法算法文本文本 T = ababcabcacbabT = ababcabcacbab模式模式 P = abcacP = abcac思想：思想：每一趟匹配出现每一趟匹配出现字符不等时，不字符不等时，不需回溯需回溯利用已得到的部利用已得到的部分匹配的结果将分匹配的结果将模式向右滑动尽模式向右滑动尽可能远的距离，可能远的距离，继续进行比较。继续进行比较。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的前缀最长匹配长度的前缀最长匹配长度nextq=maxk:kqnextq=maxk:kq且且P Pk k P Pq q P Pq q的真后缀与的真后缀与P P的前缀最长匹配长度的前缀最长匹配长度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