Hashing

Size: px

Start display at page:

Download "Hashing"

瞳懋夏
5 years ago
Views:

1 STRING MATCHING Michael Tsai 2012/06/04

2 2 問題 : 字串比對陣列 T[1..n] 中有一個長度為 n 的字串陣列 P[1..m] 中有一個長度為 m 的字串 m n 要在 T 中找 P 是否出現 P 和 T 的字串從一個字元的集合 Σ 中拿出如 : Σ = {0,1} 或 Σ = {a, b,, z} Pattern P occurs with shift s in text T (Pattern P occurs beginning at position s+1 in text T) if T s + j = P[j], for 1 j m. If P occurs with shift s in T, we call s a valid shift. Otherwise, we call s an invalid shift. 字串比對問題是要在 T 中間找到所有 P 出現的位置 (valid shift)

3 3 一些定義 Σ : 所有使用 Σ 中字元組成的有限長度字串 ( 包括長度為 0 的空字串 ) x : 字串 x 的長度 xy: 把字串 x 和 y 接起來 (concatenation) w x: 字串 w 是字串 x 的 prefix ( 也就是 x=wy, y Σ ) (w x 表示 w x ) w x: 字串 w 是字串 x 的 suffix ( 也就是 x=yw, y Σ ) (w x 表示 w x ) 例如 : ab abcca, cca abcca 空字串 ε 為任何字串的 prefix & suffix 對任何字串 x, y 和字元 a, x y iff xa ya 和為 transitive( 具遞移律 ) 的 operator

4 4 方法一 : 笨蛋暴力法 Native-String-Matcher(T, P) N=T.length M=P.length n-m+1 次 for s=0 to n-m if P[1..m]==T[s+1..s+m] print Pattern occurs with shift s O(m) O n m + 1 m

5 5 為什麼不好? 因為每次 for 執行比對, 如果錯了, 這回合的資訊完全丟掉. 例 : P=aaab 如果我們發現 s=0 是 valid shift ( 表示 T 開頭為 aaab), 那麼從之前的結果應該可以知道 shift 1, 2, 3 都可以直接跳過, 不需要一一比對. T P a a a b a a a b a a a b a a a b a a a b

6 6 方法二 : The Rabin-Karp Algorithm 假設 Σ = 0,1,, 9 那麼每個長度為 k 的字串可以想成是一個 k 位數的十進位數例如字串可以想成是十進位數把 t s 設為代表 T[s+1..s+m] 的十進位數 p 設為代表 P 的十進位數那麼 t s = p iff T[s+1..s+m]=P[1..m], 也就是 s 是 valid shift 怎麼從 P 計算 p 呢? P[1] P[2] P[3] P[m-1] P[m] p = P m + 10 P m P m P P 1

7 7 方法二 : The Rabin-Karp Algorithm 怎麼從 P 計算 p 呢? t 0 = T m + 10 T m T m T T 1 s = 0 T[1] T[2] T[3] T[m-1] T[m] T[m+1] T[m+2] 整個往右移一格 s = 1 t s+1 = 10 t s 10 m 1 T s T[s + m + 1] 拿掉最左邊那一格加上最右邊那一格

8 8 方法二 : The Rabin-Karp Algorithm 那麼用這個方法要多花少時間呢? ( 簡易分析版 ) p = O(m) P m + 10 P m P m P P 1 t 0 = O(m) T m + 10 T m T m T T 1 然後用 t s+1 = 10 t s 10 m 1 T s T[s + m + 1], 算 t 1, t 2,, t n m 的值 ( 每次都是 constant time, 共 n-m 次 ) 所以總共 : O(m) preprocessing 時間, O(n m) 比對時間

9 9 方法二 : The Rabin-Karp Algorithm 之前的兩個問題 : 1. Σ 如果是 general 的 character set, 怎麼辦? ( 不再是 {0,1,,9}) 如何解決呢? 假設 Σ = d, Σ = {c 1, c 2, c 3,, c d }. 可以把之前的式子改成 p = idx(p[m]) + d idx P m 1 + d(idx(p m 2 ) + + d idx P 2 + d idx(p 1 ) ) (a) 把整個 string 看成一個 d 進位的數. (b) 字元在 Σ 中 index 當作該字元所代表的的值

10 10 方法二 : The Rabin-Karp Algorithm 2. 當 m 比較大的時候, p 和 t s 將很難用電腦直接處理 ( 用 long long 也存不下 ) 加一加乘一乘最後總是會 overflow 如何解決? 利用同餘理論. Michael Rabin Richard Karp

11 11 同餘理論 (Modular Arithmetic) 假設 a, b 都為整數 a b mod n : 表示 a 和 b 除以 n 的餘數相等例如 : mod mod mod 5 更棒的性質 : a 1 b 1 mod n a 2 b 2 mod n 則 1. a 1 + a 2 b 1 + b 2 mod n 2. a 1 a 2 b 1 b 2 mod n 3. a 1 a 2 b 1 b 2 mod n

12 12 同餘理論 (Modular Arithmetic) a 1 b 1 mod n a 2 b 2 mod n 則 a 1 + a 2 b 1 + b 2 mod n 證明 : a 1 b 1 mod n 表示 a 1 = c a1 n + r 1 b 1 = c b1 n + r 1 a 2 b 2 mod n 表示 a 2 = c a2 n + r 2 b 2 = c b2 n + r 2 所以 a 1 + a 2 = c a1 + c a2 n + r 1 + r 2 b 1 + b 2 = c b1 + c b2 n + r 1 + r 2 兩者餘數相同! a 1 + a 2 b 1 + b 2 mod n 得證.

13 13 同餘理論 (Modular Arithmetic) a 1 b 1 mod n a 2 b 2 mod n 則 a 1 a 2 b 1 b 2 mod n 證明 : a 1 b 1 mod n 表示 a 1 = c a1 n + r 1 b 1 = c b1 n + r 1 a 2 b 2 mod n 表示 a 2 = c a2 n + r 2 b 2 = c b2 n + r 2 所以 a 1 a 2 = (c a1 n + r 1 ) c a2 n + r 2 = c a1 c a2 n + c a1 r 2 + c a2 r 1 n + r 1 r 2 b 1 b 2 = c b1 c b2 n + c b1 r 2 + c b2 r 1 n + r 1 r 2 兩者餘數相同! 得證!

14 14 The Rabin-Karp Algorithm 修正版取 q 使得 dq 可以用一個電腦 word (32-bit or 64-bit) 來表示既然 mod 後再加, 減, 乘也會保持原本的關係, 我們可以把這些 operation 都變成 mod 版本的 p = P m + d P m 1 + d P m d P 2 + dp 1 mod q t 0 = T m + d T m 1 + d T m d T 2 + dt 1 (mod q) t s+1 = d t s d m 1 T s T s + m + 1 (mod q)

15 15 The Rabin-Karp Algorithm 修正版新的 mod 版 algorithm 會造成一個問題 : 雖然 t s = p t s p mod q 但 t s = p t s p mod q 例如 mod 12, 但是如果 t s p mod q t s p 所以演算法變成這樣 : 1. 如果 t s p mod q, 那麼現在這個 s 為 invalid shift 2. 如果 t s p mod q, 那麼必須額外檢查 ( 直接比對範圍內的字串花很多時間 ) 當 t s p mod q, 但是 t s p 時, 稱為 spurious hit 當 q 夠大的時候, 希望 spurious hit 會相當少

16 例子 : Rabin-Karp Algorithm 16

17 17 Pseudo Code: Rabin-Karp Rabin-Karp-Matcher(T,P,d,q) n=t.length m=p.length h=d m 1 mod q p=0 t=0 for i=1 to m p=(dp+p[i]) mod q t=(dt+t[i]) mod q for s=0 to n-m if p==t 迴圈跑 n-m+1 次 T: string to be searched P: pattern to be matched d: size of the character set q: max number Pre-processing: O m Hit 的時候比對 : O m if P[1..m]==T[s+1..s+m] print Pattern occurs with shift s if s<n-m t=(d(t-t[s+1]h)+t[s+m+1]) mod q

18 18 Worst-case Running Time Rabin-Karp-Matcher(T,P,d,q) n=t.length m=p.length h=d m 1 mod q p=0 t=0 for i=1 to m p=(dp+p[i]) mod q t=(dt+t[i]) mod q for s=0 to n-m if p==t 迴圈跑 n-m+1 次 Worst case 的時候 : T=a n (n 個 a) P=a m (m 個 a) 比對的時間為 O(m(n-m+1)) Pre-processing: O m Hit 的時候比對 : O m if P[1..m]==T[s+1..s+m] print Pattern occurs with shift s if s<n-m t=(d(t-t[s+1]h)+t[s+m+1]) mod q

19 19 Average Running Time Rabin-Karp-Matcher(T,P,d,q) 平常的時候, valid shift 很少 n=t.length m=p.length h=d m 1 mod q p=0 t=0 Pre-processing: O m for i=1 to m p=(dp+p[i]) mod q t=(dt+t[i]) mod q 迴圈跑 n-m+1 次 for s=0 to n-m if p==t Hit 的時候比對 : O m ( 假設有 c 個 ) 不會每次都有 modulo 的 hit. 假設字串各種排列組合出現的機率相等, 則 spurious hit 的機率可當成 1/q. 則比對花的時間 : Spurious hit 共花 O( (n-m+1)/q)=o(n/q) 次總共比對花的時間為 O((n-m+1)+(m(c+n/q))) If c=o(1) and q m, O(n+m)=O(n) if P[1..m]==T[s+1..s+m] print Pattern occurs with shift s if s<n-m t=(d(t-t[s+1]h)+t[s+m+1]) mod q

20 20 方法三 : The Knuth-Morris-Pratt Algo. 一樣耶! 表示等一下可以從 P 第 4 個位置開始比 T 不用倒退! 時間複雜度會降低!

21 21 Knuth-Morris-Pratt Don Knuth James Morris Vaughan Pratt

22 22 正式一點的說法假設 P[1..q] 和 T[s+1..s+q] 已經 match 了要找出最小的 shift s 使得某個 k<q 可以滿足 P 1.. q = T s s + k, s + k = s + q If P q 是 T s+q 的 suffix s =s+(q-k) 找 P q 的最長 prefix 使得它是 T s+q 的 suffix

23 23 最好的狀況下 : 沒有重複的 pattern a b c a b f s a b c d q a b c a b f s =s+q k=0 a b c d

24 24 先處理 P 來取得重複 pattern 的資訊找 P q 的最長 prefix 使得它是 T s+q 的 suffix 找 P q 的最長 prefix P k 使得它是 P q 的 suffix 定義 Prefix function (failure function) π: Input: {1,2,,m} Output: {0,1,,m-1} π q = max k: k < q and P k is a suffix of P q ( 也就是前面例子中的 k 值, 可以想成最長的重複 pattern 的長度 )

25 25 Prefix function example π q = max k: k < q and P k is a suffix of P q i P[i] A B A B A C A π[i] π[i] i P[i] A B A B A C A B A B A B π[i] π[i]

26 26 Pseudo-code: Prefix function Compute-Prefix-Function(P) m=p.length let π[1.. m] be a new array π 1 = 0 k=0 for q=2 to m while k>0 and P[k+1]!=P[q] k=π k if P[k+1]==P[q] k=k+1 π q = k return π

27 27 例子 : Matching T=BACBABABAABCBAB i P[i] A B A B A C A π[i] 實際的 Matching Pseudo Code 和計算 prefix function 非常像請見 Cormen p KMP-Matcher

28 28 算 Prefix function 花多少時間? Compute-Prefix-Function(P) m=p.length let π[1.. m] be a new array π 1 = 0 k=0 for q=2 to m 共 O m 次 while k>0 and P[k+1]!=P[q] k=π k if P[k+1]==P[q] k=k+1 π q = k return π 麻煩的是這邊 : 總共會跳多少次呢?

29 29 Total: O(m) 算 Prefix function 花多少時間? Compute-Prefix-Function(P) m=p.length let π[1.. m] be a new array π 1 = 0 k=0 for q=2 to m while k>0 and P[k+1]!=P[q] k=π k if P[k+1]==P[q] k=k+1 π q = k return π 進入迴圈的時候 k<q, 且 q 每次增加, k 有時候不增加所以 k<q 永遠成立所以 π q = k < q. 所以每執行一次迴圈就減少 k 一次且 k 永遠不是負的 k 只會在這邊增加, 因此最多總共增加 m-1 次 ( 迴圈執行次數 ) 最後 : 既然有增加才有得減少, while loop 總共執行的次數不會超過 O(m)

30 30 KMP 執行時間類似的方法可以證明比對的部分執行時間為 O(n) 所以總和來看 : Preprocessing 時間 O(m) 比對時間 O(n)

31 31 Today s Reading Assignment Cormen ch. 32, 32.1, 32.2, 32.4 ( 正確性的證明略為複雜 )

投影片 1

投影片 1 NCKU Progrmming Contest Trining Course 08/05/09 Jheng-Hung Hong Deprtment of Computer Siene nd Informtion Engineering Ntionl Cheng Kung University Tinn, Tiwn NCKU CSIE Progrmming Contest Trining Course