Algorithm Lecture Notes PDF

ALGORITHM 2023.06.08 Hyun-Jun Kim Software Department @Chung-ang University • Algorithms – Design and Analysis • Divide and Conquer • Sorting • Selection Algorithm • Search Tree • Hash Table • Lists • Mid-Term Examination • Dynamic Programming • Graph Algorithm 1 • Graph Algorithm 2 • Greedy Alg...

ALGORITHM 2023.06.08 Hyun-Jun Kim Software Department @Chung-ang University • Algorithms – Design and Analysis • Divide and Conquer • Sorting • Selection Algorithm • Search Tree • Hash Table • Lists • Mid-Term Examination • Dynamic Programming • Graph Algorithm 1 • Graph Algorithm 2 • Greedy Algorithm • The Theory of NP • Shortest Path • Advanced Topic • Final Examination 학습목표 • 원시적인 매칭 방법에 깃든 비효율성을 감지할 수 있도록 한다. • 오토마타를 이용한 매칭 방법을 이해한다. • 라빈-카프 알고리즘의 수치화 과정을 이해한다. • KMP 알고리즘을 이해하고, 오토마타를 이용한 방법과 비교해 이점을 이해하도록 한다. • 보이어-무어 알고리즘의 개요를 이해하고, 다른 매칭 알고리즘들에 비해 어떤 특장점이 있는지 이해한다. 문자열 매칭 • 입력 – A[1…n]: 텍스트 문자열 – P[1…m]: 패턴 문자열 – m << n • 수행 작업 – 텍스트 문자열 A[1…n]이 패턴 문자열 P[1…m]을 포함하는지 알아본다 원시적인 매칭 naiveMatching(A, P) { ▷ n: 배열 A[ ]의 길이, m: 배열 P[ ]의 길이 for i ← 1 to n-m+1{ if (P[1…m] = A[i…i+m-1]) then A[i] 자리에서 매칭이 발견되었음을 알린다; } } ü 수행시간: O(mn) 원시적인 매칭의 작동원리 A[ ] b o b o 1. P[ ] s o a r s o a r s o a 2. 3. y … … c a t s o a r o p t s o a r r … … 12. 원시적인 매칭이 비효율적인 예 불일치 A[ ] . . . . . 1. 2. 3. 4. 5. 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 오토마타를 이용한 매칭 • 오토마타 (자동을 의미하는 그리스어 Αυτόματα 에서 유래) – 문제 해결 절차를 상태state의 전이로 나타낸 것 – 구성 요소: (Q, q0, A, ∑, δ) • Q : 상태 집합 • q0 : 시작 상태 • A : 목표 상태들의 집합 • ∑ : 입력 알파벳 • δ : 상태 전이 함수 • 매칭이 진행된 상태들 간의 관계를 오토마타로 표현한다 ababaca를 체크하는 오토마타 • {a,b,c,d,…z}의 원소로 구성된 문서에서 ‘ababaca’를 찾고자 함 – Q(상태들의 집합)={0,1,2,3,4,5,6,7} / q0(시작상태)=0 / A(목표상태)={7} / ∑(입력)={a,b,c,d,…z} – δ (상태 전이 함수) a a a 0 a 1 b 예) 상태 0은 아무것도 찾지 못한 상태 상태 3은 ‘aba’까지 찾은 상태 상태 7은 ‘ababaca’까지 찾은 상태 2 a a 3 b 4 a b 5 c a 6 b 7 오토마타의 SW 구현 입력문자 입력문자 상태 상태 a b c 기타 0 1 0 0 0 0 1 1 2 0 0 … 0 2 3 0 0 0 0 … 0 3 1 4 0 0 0 0 … 0 4 5 0 0 0 6 0 0 … 0 5 1 4 6 0 0 0 0 0 … 0 6 7 0 0 0 2 0 0 0 … 0 7 1 2 0 0 a b c d e … z 0 1 0 0 0 0 … 0 1 1 2 0 0 0 … 2 3 0 0 0 0 3 1 4 0 0 4 5 0 0 5 1 4 6 7 7 1 오토마타를 이용해 매칭을 체크하는 알고리즘 FA-Matcher (A, δ , f ) ▷ f : 목표 상태 { ▷ n: 배열 A[ ]의 길이 q ← 0; for i ← 1 to n { q ← δ (q, A[i]); if (q = f ) then A[i-m+1]에서 매칭이 발생했음을 알린다; } } ü 총 수행시간: Θ(n + | ∑ |m) 라빈-카프(Rabin-Karp) 알고리즘 • 문자열 패턴을 수치로 바꾸어 문자열의 비교를 수치 비교로 대신한다 • 수치화 – 가능한 문자 집합 ∑의 크기에 따라 진수가 결정된다 – 예: ∑ = {a, b, c, d, e} • |∑| = 5 • a, b, c, d, e를 각각 0, 1, 2, 3, 4에 대응시킨다 • 문자열 “cad”를 수치화 하면 2*52+0*51+3*50 = 53 • 예를 들어 “cae”를 수치화 하면 2*52+0*51+4*50 = 54 수치화 작업의 부담 • A[i…i+m-1]에 대응되는 수치의 계산 – – – – ai = A[i+m-1] + d (A[i+m-2] + d (A[i+m-3] + d (… + d (A[i]))…) Θ(m)의 시간이 든다 그러므로 A[1…n] 전체에 대한 비교는 Θ(mn)이 소요된다 원시적인 매칭에 비해 나은 게 없다 • 다행히, m의 크기에 상관없이 아래와 같이 계산할 수 있다 – ai = d(ai-1 – dm-1A[i-1]) + A[i+m-1] – dm-1은 반복 사용되므로 미리 한번만 계산해 두면 된다 – 곱셈 2회, 덧셈 2회로 충분 수치화를 이용해 매칭을 체크하는 예 basicRabinKarp(A, P, d, q) { ▷ n : 배열 A[ ]의 길이, m : 배열 P[ ]의 길이, d: 진수 p ← 0; a1 ← 0; for i ← 1 to m { ▷ a1 계산 p ← dp + P[i]; a1 ← da1 + A[i]; } for i ← 1 to n-m+1{ if (i ≠ 1) then ai ← d(ai-1 – dm-1A[i-1]) + A[i+m-1]; if (p = ai) then A[i] 자리에서 매칭이 되었음을 알린다; } } ü 총 수행시간: Θ(n) 수치화를 이용한 매칭의 예 a, b, c, d, e를 각각 0, 1, 2, 3, 4에 대응 P[ ] e e a a b A[ ] a c e b b p = 4*54 + 4*53 + 0*52 + 0*51 + 1 = 3001 c e e a a b c e e d b e e a a b c e e d b e e a a b c e e d b e a a b c e e d b a1=0*54+2*53+4*52+1*51+1 = 356 a c e b b c a2= 5(a1-0*54)+2 = 1782 a c … a c … e b b c a3=5(a2-2*54)+4 = 2664 e b b c e a7=5(a6-2*54)+1 = 3001 앞의 알고리즘의 문제점 • 문자 집합 Σ와 m의 크기에 따라 ai가 매우 커질 수 있다 – 심하면 컴퓨터 레지스터의 용량 초과 – 오버플로우 발생 • 해결책 – 나머지 연산modulo을 사용하여 ai의 크기를 제한한다 – ai = d(ai-1 – dm-1A[i-1]) + A[i+m-1] 대신 bi = (d(bi-1 – (dm-1 mod q) A[i-1]) + A[i+m-1]) mod q 사용 – q를 충분히 큰 소수로 잡되, dq가 레지스터에 수용될 수 있도록 잡는다 라빈-카프(Rabin-Karp) 알고리즘 RabinKarp(A, P, d, q) { ▷ n : 배열 A[ ]의 길이, m : 배열 P[ ]의 길이 p ← 0; b1 ← 0; for i ← 1 to m { ▷ b1 계산 p ← (dp + P[i]) mod q; b1 ← (db1 + A[i]) mod q; } h ← dm-1 mod q; for i ← 1 to n-m+1{ if (i ≠ 1) then bi ← (d(bi-1 – hA[i-1]) + A[i+m-1]) mod q; if (p = bi) then if (P[1…m] = A[i…i+m-1]) then A[i] 자리에서 매칭이 되었음을 알린다; } } ü 평균 수행시간: Θ(n) 나머지 연산을 이용한 매칭의 예 P[ ] e e a a b A[ ] a c e b b p = (4*54 + 4*53 + 0*52 + 0*51 + 1) mod 113 = 63 c e e a a b c e e d b a a b c e e d b b c e e d b c e e d b a1= (0*54+2*53+4*52+1*51+1) mod 113 = 17 a c e b b c e e a2= (5(a1-0*(54 mod 113))+2) mod 113 = 87 a c … a c … e b b c e e a a a3= (5(a2-2*(54 mod 113))+4) mod 113 = 65 e b b c e e a a b a7= (5(a6-2*(54 mod 113))+1) mod 113 = 63 KMP(Knuth-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 매칭이 실패한 경우 다음에 어디서부터 시작해야할 지에 대한 정보를 확보 KMP(Knuth-Morris-Pratt) 알고리즘 P[ ] 1 2 3 4 5 6 7 8 9 a b c d a b c w z π [8] = 4 텍스트에서 abcdabc까지는 매치되고, w에서 실패한 상황 패턴의 맨 앞의 abc와 실패 직전의 abc는 동일함을 이용할 수 있다 실패한 텍스트 문자와 P[4]를 비교한다 π[ ] 1 2 3 4 5 6 7 8 9 10 0 1 1 1 1 2 3 4 1 1 a b c d a b c w z 패턴의 각 위치에 대해 매칭에 실패했을 때 돌아갈 곳을 준비해 둔다 매칭이 실패했을 때 돌아갈 곳 준비 PMT(Partial Matching Table) P[ ] j i a b 0 0 j P[ ] j c b c w z P[ ] a b c d a b 0 0 0 0 1 2 a b c 0 0 0 j d a b c w z P[ ] a b c d 0 0 0 0 c b c d a b c 0 0 0 0 1 2 3 j a b c w z P[ ] b c d a 0 0 0 0 1 z w z i a b c d a b c w 0 0 0 0 1 2 3 0 i a w i a i j P[ ] a i j P[ ] d i j b c w z P[ ] z i a b c d a b c w z 0 0 0 0 1 2 3 0 0 매칭 작업 1 i A[ ] a b c a b c d a b b c d a b c w z c a b c d a b c d a b c w z a b c d a b d a b c w z c w z a b c c w z a b c c w z a b c j P[ ] 2 a i A[ ] a b j P[ ] 3 a b i A[ ] a b c j P[ ] a b c 매칭 작업 PMT a b c d a b c w z 0 0 0 0 1 2 3 0 0 불일치 발생 4 i A[ ] a b c a b c d a b a b c w z c w z a b c j=3 P[ ] 5 a b c d j = PMT(j-1) = PMT(2) = 0 j=0 i A[ ] a b c a b c d a b b c d a b c w z c w z a b c c w z a b c j P[ ] 6 a i A[ ] a b c a b c d a b c d a b c w z j P[ ] a b 매칭 작업 7 i A[ ] a b c a b c d a b d a b c w z c w z a b c c w z a b c c w z a b c j P[ ] 8 a b c i A[ ] a b c a b c d a b a b c w z j P[ ] 9 a b c d i A[ ] a b c a b c d a b b c w z j P[ ] a b c d a 매칭 작업 10 i A[ ] a b c a b c d a b c w z c w z a b c w z a b c z a b c j P[ ] 11 a b c d a b i A[ ] a b c a b c d a b w z c j P[ ] 12 a b c d a b c i A[ ] a b c a b c d a b j P[ ] a b c d a b c w z c w 매칭 작업 13 i A[ ] a b c a b c d a b j P[ ] a b c d a b c 시작인덱스 : i (12) – j (9) = 3 w z c w z a b c KMP(Knuth-Morris-Pratt) 알고리즘 preprocessing(P) { j ← 0; k ← 0; π [j] ← 0; while (j ≤ m) { if (k = 0 or P[j] = P[k]) then { j++; k++; π [j] ← k; } else k ← π [k]; } } 준비 작업 ü수행시간: Θ(m) KMP(Knuth-Morris-Pratt) 알고리즘 KMP(A[ ], P[ ]) { preprocessing(P); i ← 1; ▷ 본문 문자열 포인터 j ← 1; ▷ 패턴 문자열 포인터 ▷ n: 배열 A[ ]의 길이, m: 배열 P[ ]의 길이 while (i ≤ n) { if (j = 0 or A[i] = P[j]) then { i++; j++; } else j ← π [j]; //PMT if (j = m+1) then { A[i-m]에서 매치되었음을 알림; j ← π [j]; } } } ü수행시간: Θ(n) 보이어-무어(Boyer-Moore) 알고리즘 • 앞의 매칭 알고리즘들의 공통점 – 텍스트 문자열의 문자를 적어도 한번씩 훑는다 – 따라서 최선의 경우에도 Ω(n) • 보이어-무어 알고리즘은 텍스트 문자를 다 보지 않아도 된다 – 발상의 전환: 패턴의 오른쪽부터 비교한다 – Bad Character Rule, Good Suffix Rule 보이어-무어(Boyer-Moore) 알고리즘 Motivation 상황: 텍스트의 b와 패턴의 r을 비교하여 실패했다 A[ ] . . . . . . . . b P[ ] t i g e r t i g e r t i g e r 5칸을 한꺼번에 점프! ü 관찰: 패턴에 문자 b가 없으므로 패턴이 텍스트의 b를 통째로 뛰어넘을 수 있다 . . 보이어-무어(Boyer-Moore) 알고리즘 상황: 텍스트의 i와 패턴의 r을 비교하여 실패했다 A[ ] . . . . . . . t i P[ ] t i g e r t i g e r g e r . 3칸을 한꺼번에 점프! ü 관찰: 패턴에서 i가 r의 3번째 왼쪽에 나타나므로 패턴이 3칸을 통째로 움직일 수 있다 . . .