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

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

준비 작업 j k π [j] 1 2 3 4 5 6 7 8 1 0 0 a b a b a b c a a b a b a b c a 2 1 1 a b a b a b c a 2 0 1 a b a b a b c a 3 1 1 a b a b a b c a 4 2 2 a b a b a b c a 5 3 3 a b a b a b c a 6 4 4 a b a b a b c a 7 5 5 a b a b a b c a j k π [j] 1 2 3 4 5 6 7 8 7 5 5 a b a b a b c a a b a b a b c a 7 3 5 a b a b a b c a 7 1 5 a b a b a b c a 7 0 5 a b a b a b c a 8 1 1 a b a b a b c a 9 2 2 a b a b a b c a ≠ ≠ ≠

준비 작업 preprocessing(P) { π [1] = 0; j ← 1; k ← 0; while (j ≤ m) {  ▷ m: 배열 P[ ]의 길이                                 if (k = 0 or P[j] = P[k]) then { j++; k++; π [j] ← k;}            else k ← π [k]; } ~11/7/2007

보이어-무어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