쉽게배우는알고리즘 10장. 문자열매칭

Size: px

Start display at page:

Download "쉽게배우는알고리즘 10장. 문자열매칭"

해미 개
4 years ago
Views:

1 쉽게배우는알고리즘 1장. 문자열매칭

2 1장. 문자열매칭 전혀새로운아이디어를갑자기착상하는일이자주있다. 하지만그것을착상하기까지줄곧오랜동안문제를생각하고있다. 오랜동안생각한끝에갑자기답을착상하게되는것이다. - 라이너스폴링 한빛미디어

3 학습목표 원시적인매칭방법에깃든비효율성을감지할수있도록한다. 오토마타를이용한매칭방법을이해한다. 라빈 - 카프알고리즘의수치화과정을이해한다. KMP 알고리즘을이해하고, 오토마타를이용한방법과비교해이점을이해하도록한다. 보이어 - 무어알고리즘의개요를이해하고, 다른매칭알고리즘들에비해어떤특장점이있는지이해한다 한빛미디어

4 String Matching 입력 A[1n]: 텍스트문자열 P[1m]: 패턴문자열 m << n 수행작업 텍스트문자열 A[1n] 이패턴문자열 P[1m] 을포함하는지알아본다 한빛미디어

5 원시적인매칭 naivematching(a[ ], P[ ]) { n: 배열 A[ ] 의길이, m: 배열 P[ ] 의길이 for i 1 to n-m+1{ if (P[1m] = A[ii+m-1]) then A[i] 자리에서매칭이발견되었음을알린다 ; ü 수행시간 : O(mn) 한빛미디어

6 원시적인매칭의작동원리 A[ ] b o b o y c a t s o a r o p t 1. P[ ] s o a r 2. s o a r 3. s o a r 12. s o a r 한빛미디어

7 원시적인매칭이비효율적인예 불일치 A[ ]..... a b c d a b c d a b c d a b c w z P[ ] a b c d a b c w z a b c d a b c w z a b c d a b c w z a b c d a b c w z 한빛미디어

8 오토마타를이용한매칭 오토마타 문제해결절차를상태 state 의전이로나타낸것 구성요소 : (Q, q, A,, δ) Q : 상태집합 Q : 시작상태 A : 목표상태들의집합 : 입력알파벳 δ : 상태전이함수 매칭이진행된상태들간의관계를오토마타로표현한다 한빛미디어

9 ababaca 를체크하는오토마타 a a b a a a a b a c a b b S: dvganbbactababaababacabababacaagbk 한빛미디어

10 오토마타의 S/W 구현 입력문자 입력문자 상태 a b c d e z 상태 a b c 기타 한빛미디어

11 오토마타를이용해매칭을체크하는알고리즘 FA-Matcher (A, δ, f ) f : 목표상태 { n: 배열 A[ ] 의길이 q ; for i 1 to n { q δ(q, A[i]); if (q = f ) then A[i-m+1] 에서매칭이발생했음을알린다 ; ü 총수행시간 : Θ(n + m) 한빛미디어

12 라빈 - 카프 Rabin-Karp 알고리즘 문자열패턴을수치로바꾸어문자열의비교를수치비교로대신한다 수치화 가능한문자집합 의크기에따라진수가결정된다 예 : = {a, b, c, d, e = 5 a, b, c, d, e 를각각, 1, 2, 3, 4 에대응시킨다 문자열 cad 를수치화하면 2*5 2 +*5 1 +3*5 = 한빛미디어

13 수치화작업의부담 A[ii+m-1] 에대응되는수치의계산 a i = A[i+m-1] + d(a[i+m-2] + d(a[i+m-3] + d( + d(a[i]))) Θ(m) 의시간이든다 그러므로 A[1n] 전체에대한비교는 Θ(mn) 이소요된다 원시적인매칭에비해나은게없다 다행히, m의크기에상관없이아래와같이계산할수있다 a i = d(a i-1 d m-1 A[i-1]) + A[i+m-1] d m-1 은반복사용되므로미리한번만계산해두면된다 곱셈 2회, 덧셈 2회로충분 한빛미디어

14 수치화를이용한매칭의예 P[ ] e e a a b p = 4* *5 3 + *5 2 + * = 31 A[ ] a c e b b c e e a a b c e e d b a 1 =*5 4 +2*5 3 +4*5 2 +1* = 356 a c e b b c e e a a b c e e d b a 2 = 5(a 1 -*5 4 )+2 = 1782 a c e b b c e e a a b c e e d b a 3 =5(a 2-2*5 4 )+4 = 2664 a c e b b c e e a a b c e e d b a 7 =5(a 6-2*5 4 )+1 = 한빛미디어

15 수치화를이용해매칭을체크하는알고리즘 basicrabinkarp(a, P, d, q) { n : 배열 A[ ] 의길이, m : 배열 P[ ] 의길이 p ; a 1 ; for i 1 to m { a 1 계산 p dp + P[i]; a 1 da 1 + A[i]; for i 1 to n-m+1{ if (i 1) then a i d(a i-1 d m-1 A[i-1]) + A[i+m-1]; if (p = a i ) then A[i] 자리에서매칭이되었음을알린다 ; ü 총수행시간 : Θ(n) 한빛미디어

16 앞의알고리즘의문제점 문자집합 Σ 와 m 의크기에따라 a i 가매우커질수있다 심하면컴퓨터레지스터의용량초과 오버플로우발생 해결책 나머지연산modulo을사용하여 a i 의크기를제한한다 a i = d(a i-1 d m-1 A[i-1]) + A[i+m-1] 대신 b i = (d(b i-1 (d m-1 mod q)a[i-1]) + A[i+m-1]) mod q 사용 q를충분히큰소수로잡되, dq가레지스터에수용될수있도록잡는다 한빛미디어

17 나머지연산을이용한매칭의예 P[ ] e e a a b p = (4* *5 3 + *5 2 + * ) mod 113 = 63 A[ ] a c e b b c e e a a b c e e d b a 1 = (*5 4 +2*5 3 +4*5 2 +1*5 1 +1) mod 113 = 17 a c e b b c e e a a b c e e d b a 2 = (5(a 1 -*(5 4 mod 113))+2) mod 113 = 87 a c e b b c e e a a b c e e d b a 3 = (5(a 2-2*(5 4 mod 113))+4) mod 113 = 65 a c e b b c e e a a b c e e d b a 7 = (5(a 6-2*(5 4 mod 113))+1) mod 113 = 한빛미디어

18 라빈 - 카프알고리즘 RabinKarp(A, P, d, q) { n : 배열 A[ ] 의길이, m : 배열 P[ ] 의길이 p ; b 1 ; for i 1 to m { p (dp + P[i]) mod q; b 1 (db 1 + A[i]) mod q; b 1 계산 h d m-1 mod q; for i 1 to n-m+1{ if (i 1) then b i (d(b i-1 ha[i-1]) + A[i+m-1]) mod q; if (p = b i ) then if (P[1m] = A[ii+m-1]) then A[i] 자리에서매칭이되었음을알린다 ; ü 평균수행시간 : Θ(n) 한빛미디어

19 KMPKnuth-Morris-Pratt 알고리즘 오토마타를이용한매칭과동기가유사 공통점 매칭에실패했을때돌아갈상태를준비해둔다 오토마타를이용한매칭보다준비작업이단순하다 A[ ]..... a b c d a b c d..... P[ ] a b c d a b c w z a b c d a b c w z 한빛미디어

20 매칭이실패했을때돌아갈곳준비작업 P[ ] a b c d a b c w z 9 π [8] = 4 텍스트에서 abcdabc 까지는매치되고, w 에서실패한상황패턴의맨앞의 abc 와실패직전의 abc 는동일함을이용할수있다실패한텍스트문자와 P[4] 를비교한다 π [ ] a b c d a b c w z 패턴의각위치에대해매칭에실패했을때돌아갈곳을준비해둔다 한빛미디어

21 KMP 알고리즘 KMP(A[ ], P[ ]) { preprocessing(p); i 1; 본문문자열포인터 j 1; 패턴문자열포인터 n: 배열 A[ ] 의길이, m: 배열 P[ ] 의길이 while (i n) { if (j = or A[i] = P[j]) then { i++; j++; else j π [j]; if (j = m+1) then { A[i-m] 에서매치되었음을알림 ; j π [j]; ü 수행시간 : Θ(n) 한빛미디어

22 준비작업 preprocessing(p) { i 1; 본문문자열포인터 k 1; 패턴문자열포인터 while (j m) { if (k = or A[j] = P[k]) then { j++; k++; π [j] k; else k π [k]; if (j = m+1) then { A[i-m] 에서매치되었음을알림 ; j π [j]; ü 수행시간 : Θ(m) 한빛미디어

23 보이어 - 무어 Boyer-Moore 알고리즘 앞의매칭알고리즘들의공통점 텍스트문자열의문자를적어도한번씩훑는다 따라서최선의경우에도 Ω(n) 보이어 - 무어알고리즘은텍스트문자를다보지않아도된다 발상의전환 : 패턴의오른쪽부터비교한다 한빛미디어

24 Motivation 상황 : 텍스트의 b 와패턴의 r 을비교하여실패했다 A[ ] b t i g e r.. P[ ] t i g e r 다섯칸한꺼번에점프! t i g e r ü 관찰 : 패턴에문자 b 가없으므로패턴이텍스트의 b 를통째로뛰어넘을수있다 한빛미디어

25 상황 : 텍스트의 i 와패턴의 r 을비교하여실패했다 A[ ] t i g e r.... P[ ] t i g e r 세칸한꺼번에점프! t i g e r ü 관찰 : 패턴에서 i 가 r 의 3 번째왼쪽에나타나므로패턴이 3 칸을통째로움직일수있다 한빛미디어

26 점프정보준비 패턴 tiger 에대한점프정보 오른쪽끝문자 t i g e r 기타 jump 패턴 rational 에대한점프정보 오른쪽끝문자 r a t i o n a l 기타 jump 오른쪽끝문자 r t i o n a l 기타 jump 한빛미디어

27 보이어 - 무어 - 호스풀알고리즘 BoyerMooreHorspool(A[ ], P[ ]) { n : 배열 A[ ] 의길이, m : 배열 P[ ] 의길이 computeskip(p, jump); i 1; while (i n m+1) { j m; k i + m 1; while ( j > and P[j] = A[k]) { j--; k--; if (j = ) then A[i] 자리에서매칭이발견되었음을알린다 ; i i + jump[a[i + m 1]]; ü 최악의경우수행시간 : Θ(mn) ü 입력에따라다르지만일반적으로 Θ(n) 보다시간이덜든다 한빛미디어

28 불일치문자휴리스틱과일치접미부휴리스틱 a i n e r 칸점프! c a l i n t i n 3 칸점프! c a l i n t i n c a l i n t i n 4 칸점프선택! 불일치문자휴리스틱 일치접미부휴리스틱 a i n e r c a l i n t i n 한빛미디어

29 a a l e r r a t i o n a l -1 칸점프! r a t i o n a l 7 칸점프! 불일치문자휴리스틱 일치접미부휴리스틱 r a t i o n a l 7 칸점프선택! a a l e r r a t i o n a l 한빛미디어

30 Thank you 한빛미디어

ÇÐ¼ú´ëÈ¸¿Ï¼º

ÇÐ¼ú´ëÈ¸¿Ï¼º 학술대회완성 2007.9.10 11:57 PM 페이지235 사진 4 해미읍성 전경(충남 역사문화원 제공) 남문과 서문 사이에는 문헌기록에 敵臺로 표현 된 鋪樓 2개소가 길이 7.9m~7.7m, 너비 7.5m~7.6m의 규모로 만들어졌다. 성 둘레에 적이 쉽게 접근하지 못하도록 탱자나무를 돌려 심었으므로 탱자성이라는 별칭이 있었다고 한 다. 성문은 동, 서,