清华大学：《算法分析与设计》（双语版） Lecture 11 模式匹配

内容介绍 解决问题:模式匹配,对应实际问题: Lecture11模式匹配 文本文件字符串查找 格式文件中的字符串及其格式查找问题 清华大学 算法: Naive, Rabin Karp,自动机 KMP,BM算法 宋斌恒 Figure 32. 1 The string-matching problem. The goal is to 本章算法及其复杂度列表 find all occurrences of the pattern P= abaa in the text T abcabaabcabac. The pattern occurs only once in the text, at 3. The shifts=3 is said to be a valid shift. Each character of the Algorithm the text, and all matched characters are shown in green color rin pattern is connected by a vertical line to the matching charact Narve O((n-m+l)m) e(m) O(n-m+1)m) Finite automaton O(m2 text ababa bac Knuth Morris Pratt O(m) pattern P 8=3 H al bl al Terminology Lemma 32.1(Overlapping -sufix lemma) ·∑:字符集 ·∑:由Σ生成的所有字符串,包括空串的 Suppose that x, y, and z are strings such 集合以下叙述x,y,z,w表示其元素 that x ]z and y ]z If xs lyl, then x]y Concatenation of x, y: xy If x> lyl, then ]x If x= lyl, then x 前缀:[:w[x→ there exists y, such tha 后缀:]:wk→ there exists y, such that

1 1 Lecture 11 模式匹配 清华大学 宋斌恒 2 内容介绍 • 解决问题：模式匹配，对应实际问题： – 文本文件字符串查找 – 格式文件中的字符串及其格式查找问题 • 算法：Naïve，Rabin Karp, 自动机， KMP，BM算法 3 Figure 32.1 The string-matching problem. The goal is to find all occurrences of the pattern P = abaa in the text T = abcabaabcabac. The pattern occurs only once in the text, at shift s = 3. The shift s = 3 is said to be a valid shift. Each character of the pattern is connected by a vertical line to the matching character in the text, and all matched characters are shown in green color. text T pattern P b a b a a a c a b a a b c a b a c 4 本章算法及其复杂度列表 Algorithm preprocessing time matching time Naïve 0 O((n-m+1)m) Rabin-Karp Θ(m) O((n-m+1)m) Finite automaton O(m|Σ|) Θ(n) Knuth Morris Pratt O(m) Θ(n) BM 5 Terminology • Σ: 字符集 • Σ*:由Σ生成的所有字符串，包括空串的 集合,以下叙述x, y, z, w表示其元素 • Concatenation of x，y： xy • 前缀：[ : w [ x Î there exists y，such that x=wy • 后缀： ] : w ]x Î there exists y，such that x=yw 6 Lemma 32.1 (Overlapping-suffix lemma) Suppose that x, y, and z are strings such that x ] z and y ] z. If |x| ≤ |y|, then x] y. If |x| ≥ |y|, then y ] x. If |x| = |y|, then x = y

Figure 32.3 A graphical proof of Lemma 32.I. We suppose that x ]a andy 1z onnect matching regions(shown shaded) of the strings. (a)If k b then ]x()If k]=b thenx=y Naive String matching algorithm ■■ Naive-String-matcher(T, P 2.m∈ . length[P 3.Fors∈0ton-m 1. IfP[L,-,m==T[+1,.,stm 1. Print"Pattern occurs with shifts Rabin Karp algorithm Key points of Karp-Rabin Hash Value p of a string P with modulo q How to compute the value efficiently? p=hash(P, m, q(P(mEP+ P(m-121+ P( J2P+ Plm-1JIEp+.+ P[=lm-l)mod( Ls+i=Hash(T[+1,m], m, q) 计算方法:多项式求值方法 ts+i =d(ts-TIsIh)T[s+m+l] mod(g) ·算法描述: h=dm-l(mod q) 给定字符串T和要找的子字符串P d是进位,如果是26个字符,则可以是26, If Hash(P/m, q)=Hash(T(L,m,m,q)c 般来讲取d为 ·继续判断(nave方法) Spurious Hit 其中Ti,m]表示T从开始长度为m的子串 lsl9lo2|34|52|6173992山 ·mod13 89|3l084|50u7gl valid (b)

2 7 Figure 32.3 A graphical proof of Lemma 32.1. We suppose that x ] a and y ] z. The three parts of the figure illustrate the three cases of the lemma. Vertical lines connect matching regions (shown shaded) of the strings. (a) If |x| ≤ |y|, then x ] y. (b)If |x| ≥ |y|, then y ] x. (c) If |x| = |y|, then x = y. 8 Naïve String matching algorithm • Naïve-String-matcher(T,P) 1. nÅlength[T] 2. mÅlength[P] 3. For s Å0 to n-m 1. If P[1,…,m]==T[s+1,…,s+m] 1. Print “Pattern occurs with shift” s 9 Rabin Karp algorithm • Hash Value p of a string P with modulo q: – p=hash(P,m,q)=(P[m]|Σ| 0+ P[m-1]|Σ| 1+ P[m-2]|Σ| 2+…+ P[m-i]|Σ| i +…+ P[1]|Σ| m-1) mod(q) – 计算方法：多项式求值方法， • 算法描述： – 给定字符串T和要找的子字符串P， – 从i=1到Length[T]-Length[P] • If Hash(P,m,q)!=Hash(T[i,m],m,q) continue • 继续判断（naïve方法） • 其中T[i,m]表示T从i开始长度为m的子串 10 Key Points of Karp-Rabin • How to compute the value efficiently? – ts+1 = Hash(T[s+1,m],m,q) – ts+1 =(d(ts-T[s+1]h)+T[s+m+1]) mod(q) – h=dm-1 (mod q) – d是进位，如果是26个字符，则可以是26， 一般来讲取d为|Σ| • Spurious Hit 11 2 9 0 2 3 1 4 1 5 2 6 7 7 3 5 3 9 9 2 1 12 2 9 0 2 3 1 4 1 5 2 6 7 7 3 5 3 9 9 2 1 8 9 3 11 0 1 8 4 5 10 11 7 9 11

Rabin-Karp-Matcher(T, P,d, q) 1.n= length们 ld 2. m=length[Pl digit shift 3. h=dm-l(mod q) 4.p=0 6. For i=l to m 8(mod13) 1, p=(dptPo)(mod q) 2. to=(dto+T)(mod q) 7. For s=0 to n-m PI1,…,mF=s-…m+ sh print" pattem occurs I. td(t-Ts+Ih+T[s+m+l] mod(q) String matching with finite 有限自动机示例:同 有限自动机M:5uple(Q40A,x,6) Q is a finite set of states a go in Q is the start state A contains inQ is a distinguished set of accepting states 2 is a finite input alphabet 6 is a function from q×∑ into Q called the abana accepted transition function of m abbbaaa accepte abba rejected Final-state function String matching automata 中Σ*→Q M=(Qq0A,∑。) where P(E=go ∑= the alphabet in P ￠wa=6(φw,a) for w in 2*,ainΣ m: Integer s means the current state has exactly s characters match the patter m=length(PI A={m} 6:5(q1a=G(Pa)2o(x=max{kPk2x,P表示 的前k个字符,称为后缀函数。【研究!】

3 13 3 1 4 1 5 2 7 8 14152≡(31415－3·10000) · 10+2(mod 13) ≡(7－3 · 3) · 10+2(mod 13) ≡8(mod 13) 14 • Rabin-Karp-Matcher(T,P,d,q) 1. n=length[T] 2. m=length[P] 3. h=dm-1 (mod q) 4. p=0 5. T0=0 6. For i =1 to m 1. p=(dp+P[i]) (mod q) 2. t0=(dt0+T[i]) (mod q) 7. For s = 0 to n-m 1. If p=ts 1. If P[1,…,m]=T[s,…,m+s], print “pattern occurs at ” s 2. If s<n-m 1. ts+1=(d(ts-T[s+1]h)+T[s+m+1] mod(q) 15 String matching with finite automata • 有限自动机 M：5-tuple (Q,q0,A,Σ,δ) • Q is a finite set of states • q0 in Q is the start state • A contains in Q is a distinguished set of accepting states • Σ is a finite input alphabet • δ is a function from Q×Σ into Q called the transition function of M 16 有限自动机示例: 0 1 1 0 0 0 1 0 state a b input δ ? Σ ? A 1 q ? 0 Q ? abaaa accepted abbbaaa accepted abbaa rejected 17 Final-state function • φ: Σ∗ ÆQ • φ(ε)=q0 • φ(wa)=δ(φ(w),a) for w in Σ∗, a in Σ 18 String matching automata • Given pattern P, to construct an automaton: • M= (Q,q0,A,Σ,δ) where • Σ = the alphabet in P • Q = {0,1,2,…,m: integer s means the current state has exactly s characters match the pattern}, m=length[P] • q0=0 • A={m} • δ : δ(q,a)=σ(Pqa), σ(x)=max{k:Pk =x}, Pk表示P 的前k个字符，称为后缀函数。【研究！】

Automaton for“ ababa 9ab④⑤⑥ 其它转移如何做? 自动机工作的一个例子 1 3 13 02040402 34567891011 b a b a b a c a b 51 68 (T)01234545672 71 算法描述: 后缀函数σ的属性: 【引定理32.2/3/4】 Finite-Automaton- Matcher(T, 8, m) If q=o(x)then o(xa=o(Poa) 6q,T) 如果ψ是模式P决定的自动机的最终状态 2. If q==m then print"pattern occurs at"i-m 函数,则(T=0(T

4 19 Automaton for “ababaca” 0 1 2 3 4 5 6 7 其它转移如何做？ 转移函数？ 20 0 1 2 3 4 5 6 7 21 1 0 0 1 2 0 3 0 0 1 4 0 5 0 0 1 4 6 7 0 0 1 2 0 22 自动机工作的一个例子 i — 1 2 3 4 5 6 7 8 9 10 11 T[i] — a b a b a b a c a b a stateφ(Ti ) 0 1 2 3 4 5 4 5 6 7 2 3 23 算法描述： • Finite-Automaton-Matcher(T,δ,m) 1. n=length[T] 2. q=0 3. For i = 1 to n 1. q=δ(q,T[i]) 2. If q==m then print “pattern occurs at” i-m 24 后缀函数σ的属性： 【引/定理32.2/3/4】 • σ(xa)≤ σ(x)+1 • If q= σ(x) then σ(xa)=σ(Pqa) • 如果φ是模式P决定的自动机的最终状态 函数，则φ(Ti )=σ(Ti )

■ ■■口 Figure 32.8 An illustration for the proof of Lemma 32.2. The figure shows thats o(x)+ l, where r= o(xa) Figure 32.9 An illustration for the proof of Lemma 32.3 The figure shows thatr=o(Pa), where q=o(x) and r=o(xa) COMPUTE-TRANSITION-FUNCTION(P, 2) Knuth-Morris-Pratt Algorithm 7 mlength[PI 2forq←0tom ·中心思想:克服nave算法和有限自动机 3 do for each character a∈∑ 算法的重复工作! do k- min(m+1, 9+2) ·主要步骤:计算辅助函数π{1,2,,m它只 repeat k←k 与 Pattern相关,用来说明 Pattern的重复情 until Pk]P4【是后缀! 7 6q,a)←k 8 return 5 在某S处开始有5个字符匹配,第六个不匹配 这时找一个短一些的匹配串:即从第S+2处开 始的长度为3的地方匹配见下页 balc babr bac bababaa babr H blal lacal aa bl a ca

5 25 Figure 32.8 An illustration for the proof of Lemma 32.2. The figure shows that r ≤ σ(x) + 1, where r = σ(xa). pr−1 pr 26 Figure 32.9 An illustration for the proof of Lemma 32.3. The figure shows that r = σ(Pqa), where q = σ(x) and r = σ(xa). pq pr 27 COMPUTE-TRANSITION-FUNCTION(P, ∑) 1 m←length[P] 2 for q ← 0 to m 3 do for each character a ∈ ∑ 4 do k ← min(m + 1, q + 2) 5 repeat k ← k － 1 6 until Pk ] Pqa【是后缀！】 7 δ(q, a) ← k 8 return δ 28 Knuth-Morris-Pratt Algorithm • 中心思想：克服naïve 算法和有限自动机 算法的重复工作！ • 主要步骤：计算辅助函数π[1,2,…,m]它只 与Pattern相关，用来说明Pattern的重复情 况。 29 a a b a a b c b a b a b a a b c b a b b c a 在某S处开始有5个字符匹配，第六个不匹配， 这时找一个短一些的匹配串：即从第S＋2处开 始的长度为3的地方匹配,见下页 30 a a b a a b c b a b a b a a b c b a b b c a

2|34|5678|91 r ba blabla al x17|002345|60 P a aba KMP-MATCHER(T, P) 2 m+lengthIP Lalblalblablabea N+COMPUTE-PREFIX-FUNCTION(P D Number of characters matched I blabber do while q>0 and Pla+11≠ D Next character does not match ifP1a+1]=T0 then g-g+I D Next character matches D Is all of p matched 8 ia bb a be a x 2-o then print“ Pattem occurs with shift”-m D Look for the next match. COMPUTE-PREFIX-FUNCTION(P) BM算法 2t[l]←0 he Boyer-Moore algorithm 4forq←2tom 5 do while k>0 and PIk+1]= plal 种从右边开始进行匹配的算 dok←r[k 法 if P[k +1]=Plal then k←k+1 rq]←k l0 returnπt 6

6 31 a b a a b a b a Pq Pk 32 1 2 3 4 5 6 7 8 9 10 a b a b a b a b c a 0 0 1 2 3 4 5 6 0 1 33 a b a b a b a b a b a b a b a b a b a b P8 P6 P4 P2 P0 c a a b c a π[8]=6 a b a b c a π[6]=4 a b a b a b c a π[4]=2 ε a b a b a b a b c a π[2]=0 34 KMP-MATCHER(T, P) 1 n←length[T] 2 m←length[P] 3 π←COMPUTE-PREFIX-FUNCTION(P) 4 q ← 0 Number of characters matched. 5 for i ← 1 to n Scan the text from left to right. 6 do while q > 0 and P[q + 1] ≠ T[i] 7 do q ← π[q] Next character does not match. 8 if P[q + 1] = T[i] 9 then q ← q + 1 Next character matches. 10 if q = m Is all of P matched? 11 then print “Pattern occurs with shift” i － m 12 q ← π[q] Look for the next match.       35 COMPUTE-PREFIX-FUNCTION(P) 1 m←length[P] 2 π[1] ← 0 3 k ← 0 4 for q ← 2 to m 5 do while k > 0 and P[k + 1] ≠ P[q] 6 do k ← π[k] 7 if P[k +1] = P[q] 8 then k ← k +1 9 π[q] ← k 10 return π 36 BM算法 • The Boyer-Moore algorithm • 一种从右边开始进行匹配的算 法

主要思想 坏字符试探 从右向左比 革您字奔箬忠安數 Bad character heuristics 第一个字符不匹配 革 0123456789 且目标串的第一个字符在模式串的其它 abbadia baba 位置出现,在这种情况下,模式串右移 模式串 ba bac 到其相应字符与目标串第一个字符匹配 babac 的位置上。 示例 Good suffix heuristics 位置0123456789 位置0123456789 目标串 a bb a b ab acba 目标串 a b a ab cba 模式串 b a b ac 模式串 c a b a b b a b a c c a b a b 导致不匹配,但目标串字符b出现在模 目标串和模式串的后缀ab已匹配,模 其最右边的字符b和目标串的第一个字 式串应当右移2位,使其从右至左的第 符b匹配 个子串ab与目标串的后缀ab匹配 Good suffix heuristics Good suffix heuristics 下面这个例子中,同样目标串和模式 目标串和模式串的后缀bab已匹配,在位置 串的后缀ab已匹配,但子串ab没有在模 有再出现在 式串的其它位置出现。所以模式串可以 右移5位 位置0123456789 bab)的后缀匹配 位置0123456789 目标串 ab c a cba 目标串 aa b a b a cba 模式串cbaa 模式串 a bb a b cb a ab a bb a b

7 37 主要思想 从右向左比： 当目标串中的字符根本就没有在模式串中出现，模 式串就可以从这一字符开始向右移动m位置数。 例子：位置 0 1 2 3 4 5 6 7 8 9 … 目标串 a b b a d a b a c b a 模式串 b a b a c b a b a c 这种算法最好的情况就是模式串每一次和目标串比 较，它们第一个字符就不匹配，且目标串中的字符不 在模式串中出现，这样模式串每一次都可移动m位。 38 坏字符试探 Bad character heuristics 目标串和模式串第一个字符不匹配， 且目标串的第一个字符在模式串的其它 位置出现，在这种情况下，模式串右移 到其相应字符与目标串第一个字符匹配 的位置上。 39 示例 位置 0 1 2 3 4 5 6 7 8 9 … 目标串 a b b a b a b a c b a 模式串 b a b a c b a b a c b-c导致不匹配，但目标串字符b出现在模 式串的位置0和位置2，于是模式串可右移2 位，使其最右边的字符b和目标串的第一个字 符b匹配。 40 Good suffix heuristics 位置 0 1 2 3 4 5 6 7 8 9 … 目标串 a b a a b a b a c b a 模式串 c a b a b c a b a b √ 目标串和模式串的后缀ab已匹配，模 式串应当右移2位，使其从右至左的第二 个子串ab与目标串的后缀ab匹配。 41 Good suffix heuristics 下面这个例子中，同样目标串和模式 串的后缀ab已匹配，但子串ab没有在模 式串的其它位置出现。所以模式串可以 右移5位。 位置 0 1 2 3 4 5 6 7 8 9 … 目标串 a b c a b a b a c b a 模式串 c b a a b c b a a b 42 Good suffix heuristics 目标串和模式串的后缀bab已匹配，在位置 1出现a-b不匹配，同时子串bab也没有再出现在 模式串中，但在这种情形下模式串不能象上一 种情形右移5位，而只能右移3位，因为模式串 的前缀ab和子串bab（也就是目标串的子串 bab）的后缀匹配。 位置 0 1 2 3 4 5 6 7 8 9 … 目标串 a a b a b a b a c b a 模式串 a b b a b a b b a b

对“坏字符情况的预处理 算法: 对于这种情况,我们首先定义一 fora←0 to alphabets 的每一个字符在模式串中出现的最右 置,如果根本没有出现在模式串中 forj·otom 定义 j|p,=a}如果a出现在模式串中 如果a没有在模式串中出现 occa 例子: 其中p0P1pm代表模式串,a是广义字母 occ(text, x)=2 表中的任一字符。 occ(text, t)=3 对“好后缀”情况的预处理 对“好后缀”情况的预处理 第一种情形:已匹配的后缀子串在模式串的 其它位置又出现。 我们也要建立一个数组s。数组里的 第项代表不匹配发生在模式串的位置i-1 (即模式串位置i始的后缀已和目标串 相应子串匹配)时模式串应当右移的位 01234567 然后再建立一个数组f。第项代表模 a b aa b 式串中从位置开始的后缀其最长边界开 ipfs 56456778 始的位置 00002041 对“好后缀”情况的预处理 bmPreprocessl () BM预处理算法 第二种情形:已匹配的后缀子串仅仅有一部 分又出现在模式串的开头。 do while j<=m and p[i-l*pl-I] BM检紫算法 hile j=o and pD=at(l+il 例子::01234567 bmPreprocess20 p f:56456778 0cb5 e i-i+max闻s s:55552541 then+fDl

8 43 对“坏字符”情况的预处理 对于这种情况，我们首先定义一个函数occ 生成一个数组，在这个数组中记录广义字母表 的每一个字符在模式串中出现的最右边的位 置，如果根本没有出现在模式串中，则记-1。 定义： 其中p0 p1…pm -1代表模式串，a是广义字母 表中的任一字符。 -1 a max{ j | p = a} a occ(p,a) = j ⎪⎩ ⎪ ⎨ ⎧ 如果 没有在模式串中出现 如果 出现在模式串中 44 算法： bmInitocc() for a ← 0 to alphabetsize do occ[a] ← -1 for j ← 0 to m do a ← p[j] occ[a] ← j 例子： occ(text, x) = 2 occ(text, t) = 3 45 对“好后缀”情况的预处理 我们也要建立一个数组s。数组里的 第i项代表不匹配发生在模式串的位置i-1 （即模式串位置i开始的后缀已和目标串 相应子串匹配）时模式串应当右移的位 数。 然后再建立一个数组f。第i项代表模 式串中从位置i开始的后缀其最长边界开 始的位置。 46 对“好后缀”情况的预处理 第一种情形：已匹配的后缀子串在模式串的 其它位置又出现。 i: 0 1 2 3 4 5 6 7 p: a b b a b a b f: 5 6 4 5 6 7 7 8 s: 0 0 0 0 2 0 4 1 47 对“好后缀”情况的预处理 第二种情形：已匹配的后缀子串仅仅有一部 分又出现在模式串的开头 。 例子：i: 0 1 2 3 4 5 6 7 p: a b b a b a b f: 5 6 4 5 6 7 7 8 s: 5 5 5 5 2 5 4 1 48 bmPreprocess1（） i ← m j ← m+1 f[i] ← j while i>0 do while j=0 and p[j]==t[I+j] do j ← j-1 if j<0 then return i i ← i+s[0] else i ← i+max(s[j+1],j￾occ[t[i+j]])

总结 BM算法也将匹配过程分为了对模式串的预 处理阶段 preprocessing),和检索( Searching阶 般情况下,算法的时间复杂度是O(n) 在可选的字符数量远远大于模式串的长度 时,由于这将通常导致“坏字符”情况,模式串 即可右移m个位置,因此算法的时间复杂 度平均可以达到Omn/m)

9 49 总结 BM算法也将匹配过程分为了对模式串的预 处理阶段(preprocessing)，和检索(Searching)阶 段。 一般情况下，算法的时间复杂度是O (n)。 在可选的字符数量远远大于模式串的长度 时，由于这将通常导致“坏字符”情况，模式串 一次即可右移m个位置，因此算法的时间复杂 度平均可以达到O (n/m)