쉽게 배우는 알고리즘 10장. 문자열 매칭 http://academy.hanb.co.kr

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

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

String Matching 입력 수행 작업 A[1…n]: 텍스트 문자열 P[1…m]: 패턴 문자열 m << n

원시적인 매칭 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 y c a t s o a r o p t 1. P[ ] s o 2. s o a r 3. … … … … s o a r 12.

원시적인 매칭이 비효율적인 예 . a b c d a b c d w z a b c d w z a b c d w z a b c d 불일치 A[ ] . a b c d 1. a b c d w z P[ ] 2. a b c d w z a b c d w z 3. 4. a b c d w z 5. a b c d w z

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

ababaca를 체크하는 오토마타 S: dvganbbactababaababacabababacaagbk… 1 2 3 4 5 6 1 2 3 4 5 6 7 b b S: dvganbbactababaababacabababacaagbk…

오토마타의 S/W 구현 입력문자 입력문자 상태 상태 a b c d e … z a b c 기타 1 … 1 2 3 4 5 6 7 1 1 2 … 1 2 3 … 2 3 1 4 … 3 4 5 … 4 5 1 4 6 … 5 6 7 … 6 7 1 2 … 7

오토마타를 이용해 매칭을 체크하는 알고리즘 FA-Matcher (A, δ , 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 = 28

수치화 작업의 부담 A[i…i+m-1]에 대응되는 수치의 계산 다행히, m의 크기에 상관없이 아래와 같이 계산할 수 있다 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회로 충분

수치화를 이용한 매칭의 예 … … e a b a c e b d a c e b d a c e b d a c e b d P[ ] a2= 5(a1-0*54)+2 = 1782 a c e b d … a3=5(a2-2*54)+4 = 2664 a c e b d … a7=5(a6-2*54)+1 = 3001

수치화를 이용해 매칭을 체크하는 알고리즘 basicRabinKarp(A, P, d, q) { p ← 0; a1 ← 0; ▷ n : 배열 A[ ]의 길이, m : 배열 P[ ]의 길이    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)

앞의 알고리즘의 문제점 문자 집합 Σ와 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가 레지스터에 수용될 수 있도록 잡는다

나머지 연산을 이용한 매칭의 예 … … e a b a c e b d a c e b d a c e b d a c e b d P[ ] e a b p = (4*54 + 4*53 + 0*52 + 0*51 + 1) mod 113 = 63 A[ ] a c e b d a1= (0*54+2*53+4*52+1*51+1) mod 113 = 17 a c e b d a2= (5(a1-0*(54 mod 113))+2) mod 113 = 87 a c e b d … a3= (5(a2-2*(54 mod 113))+4) mod 113 = 65 a c e b d … a7= (5(a6-2*(54 mod 113))+1) mod 113 = 63

라빈-카프 알고리즘 RabinKarp(A, P, d, q) { p ← 0; b1 ← 0; ▷ 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)

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

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

KMP 알고리즘 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]; if (j = m+1) then {                 A[i-m]에서 매치되었음을 알림;                 j ← π [j];                      }  } 수행시간: Θ(n)

준비 작업 preprocessing(P) { i ← 1; ▷ 본문 문자열 포인터 k ← 1; ▷ 패턴 문자열 포인터 while (j ≤ m) {                                  if (k = 0 or A[j] = P[k]) then { j++; k++; π [j] ← k; }            else k ← π [k]; if (j = m+1) then {                 A[i-m]에서 매치되었음을 알림;                 j ← π [j];                      }  } ~11/7/2007 수행시간: Θ(m)

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

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

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

점프 정보 준비 패턴 “tiger”에 대한 점프 정보 패턴 “rational”에 대한 점프 정보 오른쪽 끝문자 t i g e 기타 jump 4 3 2 1 5 패턴 “rational”에 대한 점프 정보 오른쪽 끝문자 r a t i o n l 기타 jump 7 6 5 4 3 2 1 8 오른쪽 끝문자 r t i o n a l 기타 jump 7 5 4 3 2 1 8

보이어-무어-호스풀 알고리즘 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 > 0 and P[j] = A[k]) {        j--; k--;  } if (j = 0) then A[i] 자리에서 매칭이 발견되었음을 알린다; i ← i + jump[A[i + m − 1]];                 최악의 경우 수행시간: Θ(mn) 입력에 따라 다르지만 일반적으로 Θ(n)보다 시간이 덜 든다

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

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

Thank you