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

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

2、 T b b c c a aa ab b a a a a b b c c a a b b a a c c 模式模式 P P a a b b a a a a s = 3s = 3 3 3 字符串匹配算法字符串匹配算法 朴素算法朴素算法 Rabin-KarpRabin-Karp算法算法 有限自动机算法有限自动机算法 KMPKMP算法算法 4 4 朴素算法朴素算法 模式模式 P1.mP1.m 0sn-m, Ts+1.s+m = P1.m0sn-m, Ts+1.s+m = P1.m 思想：思想： P1.mP1.m T1.nT1.n 文本文本 T1.nT1.n s=0s=0 s=1s=1s=n-ms=n

3、-m 5 5 ？ 文本文本 T = ababcabcacbabT = ababcabcacbab模式模式 P = abcacP = abcac s = 0s = 0 a a b ba ab bc ca ab bc ca ac cb ba ab b a ab bc ca ac ca ab bc ca ac c s = 1s = 1 a ab bc ca ac c s = 2s = 2 s =3 s =3 a ab bc ca ac c s =4 s =4 a ab bc ca ac c s =5 s =5 a ab bc ca ac c T(n) = O(n-m+1)m) T(n) = O(n-

4、m+1)m) 6 6 7 7 字符串匹配算法字符串匹配算法 朴素算法朴素算法 Rabin-KarpRabin-Karp算法算法 有限自动机算法有限自动机算法 KMPKMP算法算法 7 7 Rabin-KarpRabin-Karp算法算法 字符串字符串3141531415 = 0,1,29 = 0,1,29 十进制数十进制数 3141531415 映射映射 数值数值t ts s 模式模式 P1.mP1.m 思想：思想： 文本子串文本子串 Ts+1.s+mTs+1.s+m 映射映射 数值数值p p 0sn-m 0sn-m 有效偏移为有效偏移为s s Ts+1.s+m = P1.mTs+1.s+m

5、= P1.m p =tp =ts s ？ 8 8 文本文本 T = 258569236589780T = 258569236589780 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

6、 ts+1 s+1 ？ = 0,1,29 = 0,1,29 9 9 运用霍纳法则运用霍纳法则 t ts+1 s+1= d(t = d(ts s - d- dm-1 m-1Ts+1) + Ts+m+1 Ts+1) + Ts+m+1 d = |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

7、 23 36 65 5 p = 5+10p = 5+10* *(6+10(6+10* *(3+10(3+10* *2)=2365 2)=2365 文本文本 T T 2 25 58 85 56 69 92 23 36 65 58 89 97 78 80 0 t 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 = 10 t 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

8、 3* *5)+9 =8569 5)+9 =8569 t t6 6= 10(t= 10(t5 5-10-103 3* *9)+5 =2365 9)+5 =2365 预处理时间预处理时间 O(m)O(m) 1010 = Pm + d Pm-1 + d = Pm + d Pm-1 + d2 2Pm-2 + + dPm-2 + + dm-2 m-2P2 + d P2 + dm-1 m-1 P1 P1 pp%q tpp%q ts s t ts s%q %q 问题：问题：p p和和t ts s的值可能太大的值可能太大方法：方法：p p和和t ts s的值取模的值取模q q t ts+1 s+1 = (

9、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 1111 for i=1 to mfor i=1 to m p = (dp+Pi)%qp = (dp+Pi)%q t ts+1 s+1= d(t = d(ts s - d- dm-1 m-1Ts+1) + Ts+m+1 Ts+1) + Ts+m+1 d = |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

10、%c)(b%c)%c t ts+1 s+1=d(t =d(ts s - d- dm-1 m-1Ts+1) + Ts+m+1 Ts+1) + Ts+m+1 %q%q =( d(t=( d(ts s-Ts+1h)+Ts+m+1 )%q -Ts+1h)+Ts+m+1 )%q (d(dm-1 m-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 %q 1212 若若t ts sp p Ts+1.s+mTs+1.s+m与模式与模式P P不匹配，偏移不匹配，偏移s

11、 s无效无效 若若t ts s=p=p P P与与T T成功匹配成功匹配 s s为有效偏移为有效偏移 Ts+1.s+m = P1.mTs+1.s+m = P1.m Ts+1.s+m P1.mTs+1.s+m P1.m P P与与T T不匹配不匹配 s s为伪命中点为伪命中点 3 31 14 41 15 52 2 q=13q=13 t ts+1 s+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 =

12、31415%13 = 7 = 7 t ts+1 s+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=2359023141526739921T=2359023141526739921 p=31415%13 = 7p=31415%13 = 7 模式模式P=31415P=31415 2 23 35 59 90 02 23 31 14 41 15 52 26 67 73 39 99 92 21 1 8 89 93 311 11 0 01 17 78 84 45 51010 1

13、1 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-m+1+cm)=O(n+m) t ts+1 s+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=8 1313 字符串匹配算法字符串匹配算法 朴素算法朴素算法 Rabin-KarpRabin-Karp算法算法 有限自动机算法有限自

14、动机算法 KMPKMP算法算法 1414 有限自动机有限自动机 定义定义: : 有限自动机有限自动机MM5 5元组元组(Q,q(Q,q0 0,A,A, ,) ) Q Q是状态的有限集合是状态的有限集合 q q0 0QQ是初始状态是初始状态 A Q A Q是接受状态集合是接受状态集合 是是MM的转移函数的转移函数 是有限输入字母表是有限输入字母表 QQ QQ P 1.mP 1.m Q=0,1,mQ=0,1,m q q0 0=0=0 A = mA = m 1 10 0 0 00 0 0 0 1 1 状态状态 输入输入 a ba b =a,b=a,b (1,b)=0(1,b)=0 (0,a)=1(0

15、,a)=1 1515 思想：思想： 构造模式构造模式P P的字符串匹配自动机的字符串匹配自动机 逐个扫描文本逐个扫描文本T T中字符，记录终止状态中字符，记录终止状态 状态状态q qA A时，得到一个匹配时，得到一个匹配 1616 构造有限自动机构造有限自动机 a ab ba ac c 模式模式P P 前缀，后缀，真前缀，真后缀前缀，后缀，真前缀，真后缀 P P的前缀与的前缀与x x的后缀的最长匹配长度的后缀的最长匹配长度 (ccaba)=3(ccaba)=3 ( ()=0)=0 (ccab)=2(ccab)=2 P P3 3=aba P=aba P P P4 4=abac P =abac P

16、 ac Pac P 模式模式P P的后缀函数的后缀函数 (x)=maxk: P(x)=maxk: Pk k x k0,m x k0,m 1717 构造有限自动机构造有限自动机 字符串匹配自动机字符串匹配自动机 模式模式P1.mP1.m 状态集合状态集合Q=0,1,mQ=0,1,m 初始状态初始状态q q0 0=0=0 接受状态接受状态A=mA=m 记录记录P P的前缀与所读入的前缀与所读入T Ti i后缀的最长匹后缀的最长匹 配长度配长度 a ab ba ab ba ac ca a模式模式P P 状态状态 输入输入 a b c a b c 0 0 1 1 2 2 3 3 4 4 5 5 6 6

17、 7 7 1 10 00 0 1 12 20 0 3 30 00 0 1 14 40 0 5 50 00 0 1 14 46 6 7 70 00 0 1 12 20 0 q =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)=(ac)=0(ac)=0 q =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

18、 (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 1818 a ab ba ab ba ac ca a模式模式P P 输入输入 a b c a b c 状态状态 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 1 10 00 0 1 12 20 0 3 30 00 0 1 14 40 0 5 50 00 0 1 14 46 6 7 70 00 0 1 12 20 0 文本文本T T a ab ba ab ba

19、 ab ba ac ca ab ba a 0 01 12 23 34 45 54 45 56 67 72 23 3 a a 0 01 12 23 34 45 56 67 7 a a a a b ba aa ab bc ca a b b b b a a a a 匹配时间匹配时间T(n) = O(n)T(n) = O(n) 1919 计算转移函数计算转移函数 预处理时间预处理时间T(n) =O(mT(n) =O(m3 3| |)|) compute-transition-function(P,compute-transition-function(P,) ) m=P.lengthm=P.lengt

20、h for for q=0 to mq=0 to m forfor each charater a each charater a k=min(m+1,q+2)k=min(m+1,q+2) repeatrepeat k =k-1k =k-1 untiluntil P Pk k P Pq qa a (q,a) = k(q,a) = k return return 2020 字符串匹配算法字符串匹配算法 朴素算法朴素算法 Rabin-KarpRabin-Karp算法算法 有限自动机算法有限自动机算法 KMPKMP算法算法 2121 KMPKMP算法算法 文本文本 T = ababcabcacbab

21、T = ababcabcacbab模式模式 P = abcacP = abcac 思想：思想：每一趟匹配出现每一趟匹配出现 字符不等时，不字符不等时，不 需回溯需回溯 利用已得到的部利用已得到的部 分匹配的结果将分匹配的结果将 模式向右滑动尽模式向右滑动尽 可能远的距离，可能远的距离， 继续进行比较。继续进行比较。 a ab bc ca ac c a ab ba ab bc ca ab bc ca ac cb ba ab b文本文本T T 模式模式P P 2222 文本文本T T b ba ac cb ba ab ba ab ba aa ab bc cb ba a s= 4s= 4 a ab

22、ba ab ba ac ca a模式模式P P s s = 6 = 6 a ab ba ab ba ac ca a a ab ba ab ba a P P5 5 a ab ba a P P3 3 next5=3next5=3 s s =s+(5-next5) =s+(5-next5) s s = s +(q-nextq) = s +(q-nextq) 2323 P Pq q的真后缀与的真后缀与P P的前缀最长匹配长度的前缀最长匹配长度 nextq=maxk:kqnextq=maxk:kq且且P Pk k P Pq q P Pq q的真后缀与的真后缀与P P的前缀最长匹配长度的前缀最长匹配长度

23、a ab ba ab ba ac ca a next1=0next1=0 next2=0next2=0 a ab ba ab ba ac ca a a ab ba ab ba ac ca a next3=1next3=1 a ab ba ab ba ac ca a a ab ba ab ba ac ca aa ab ba ab ba ac ca a a ab ba ab ba ac ca a next4=2next4=2 next5=3next5=3 next6=0next6=0 next7=1next7=1 a ab ba ab ba ac ca a a ab ba ab ba ac ca a a ab ba ab