• 검색 결과가 없습니다.

제10장 문자열 매칭

N/A
N/A
Protected

Academic year: 2021

Share "제10장 문자열 매칭"

Copied!
16
0
0

로드 중.... (전체 텍스트 보기)

전체 글

(1)

http://academy.hanb.co.kr

10장. 문자열 매칭

2 -IT COOKBOOK IT COOKBOOK 한빛미디어㈜

10장. 문자열 매칭

새로운 생각이나 새로운 발전이 이루어지는 직관의 도약이 있다. 이렇게 순간적으로 튀어 오르는 힘이 유난히 좋은 과학자들이 있다. 특별히 뛰어난 직관력을 가진 과학자들을 보면 마치 종교인들이 말하는 것과 같은 그런 종류의 믿음이 있다. 그들의 마음을 사로잡는 어떤 것이 이끄는 곳으로 흔들림 없이 그대로 따라가는 성향은 최정상의 과학자가 흔히 보이는 특성이다. - 프리초프 카프라 전혀 새로운 아이디어를 갑자기 착상하는 일이 자주 있다. 하지만 그것을 착상하기까지 줄곧 오랜 동안 문제를 생각하고 있다. 오랜 동안 생각한 끝에 갑자기 답을 착상하게 되는 것이다. - 라이너스 폴링

(2)

- 3 - 한빛미디어㈜

학습목표

• 원시적인 매칭 방법

에 깃든 비효율성을 감지할

수 있도록 한다

.

• 오토마타를 이용한 매칭 방법

을 이해한다

.

• 라빈-카프 알고리즘

의 수치화 과정을 이해한다

.

• KMP 알고리즘

을 이해하고

, 오토마타를 이용

한 방법과 비교해 이점을 이해하도록 한다

.

• 보이어-무어 알고리즘

의 개요를 이해하고

, 다

른 매칭 알고리즘들에 비해 어떤 특장점이 있

는지 이해한다

.

IT COOKBOOK IT COOKBOOK

String Matching

• 입력

– A[1…n]: 텍스트 문자열 – P[1…m]: 패턴 문자열 – m << n: 즉, A[]가 P[]보다 현저히 길다고 가정

• 수행 작업

– 텍스트 문자열 A[1…n]이 패턴 문자열 P[1…m]을 포함하는지 알아본다

(3)

- 5 - 숙명여대 멀티미디어과학과

원시적인 매칭

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] 자리에서 매칭이 발견되었음을 알린다;

}

}

9

수행시간: O(mn)

- 6 - 숙명여대 멀티미디어과학과 IT COOKBOOK IT COOKBOOK t p o r a o s t a c y o b o b A[ ] r a o s r a o s r a o s P[ ] r a o s

1. 2. 3. 12. …

원시적인 매칭의 작동 원리

(4)

- 7 - 숙명여대 멀티미디어과학과 . . . a b c d a b c d . . . . . a b c d a b c w z a b c d a b c w z A[ ] 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 1 2 3 4 5 불일치

원시적인 매칭이 비효율적인 예

9그림에서2, 3, 4를 건너 뛸 수 있는 방안이 있나? 9P[5…7]과 P[1…3]이 일치한다는 사실을 이용 한다면? IT COOKBOOK IT COOKBOOK

오토마타를 이용한 매칭

• 오토마타

– 문제 해결 절차를 상태

state

의 전이로 나타낸 것

– 구성 요소: (Q, q

0

, F, ∑, δ)

• Q : 상태들의 집합 • q0: 오토마타의 작동이 시작되는 상태 • F : 목표 상태(목적이 달성된 상태)들의 집합 • ∑ : 입력 가능한 문자 집합 • δ : 상태 전이 함수

• 매칭이 진행된 상태들간의 관계를 오토마타로

표현한다

.

(5)

- 9 - 숙명여대 멀티미디어과학과

ababaca

를 체크하는 오토마타

0

a

1

b

2

a

3

b

4

a

5

6

a

7

b c b a a a a

S: dvganbbactababa

ababaca

b

ababaca

agbk…

• 오토마타 구성 예

– Q = {0, 1, 2, 3, 4, 5, 6, 7} – q0= 0 – F = {7} – ∑ = {a, b, c, d, …, z} – δ : 오토마타 상태 전이 그림에서 만들 수 있음 - 10 - 숙명여대 멀티미디어과학과 IT COOKBOOK IT COOKBOOK 0 2 1 3 4 5 6 7 a b c 0 2 1 0 0 7 6 4 1 0 0 5 0 4 1 0 0 3 0 2 1 0 0 1 상태 입력문자 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 … … … … … … … … d e … z

테이블을 이용한 오토마타 상태 전이 함수

δ

의 구현

해석 예

: δ(3, b) = 4, 상태 3에서 문자 ‘b’를 입력으로 받으면

상태

4로 이동한다는 의미

(6)

- 11 - 숙명여대 멀티미디어과학과

오토마타를 이용해 매칭을 체크하는 알고리즘

FA-Matcher (A, δ , f )f : 목표 상태 { ▷n: 배열 A[ ]의 길이 q = 0;q: 현재 상태를 나타내는 변수 for i ← 1 to n { q ← δ (q, A[i]); if (q == f ) then A[i-m+1]에서 매칭이 발생했음을 알린다; } } 9 총 수행시간: Θ(n + |∑|m) IT COOKBOOK IT COOKBOOK 0 2 1 3 4 5 6 7 a b c 0 2 1 0 0 7 6 4 1 0 0 5 0 4 1 0 0 3 0 2 1 0 0 1 상태 입력문자 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 … … … … … … … … d e z

상태 전이 함수 크기 줄이기

0 2 1 3 4 5 6 7 a b c 1 0 0 0 1 2 0 0 3 0 0 0 1 4 0 0 5 0 0 0 1 4 6 0 7 0 0 0 1 2 0 0 기타 상태 입력문자

• 패턴 P[1…m]에 포함된 문자들만으로

입력가능 집합을 구성

– ∑ = {a, b, c, d, …, z} Î ∑’ = {a, b, c} – 그런 후 상태 s에서 문자 r을 만나는 경우에 상태 전이함수 계산 시δ(s, r) 대신 δ(s, i[r])을 사용한다. 1 2 3 4 4 4 4 i[ ] a b c d e f … z

(7)

- 13 - 숙명여대 멀티미디어과학과

라빈

-카프

Rabin-Karp

알고리즘

• 문자열 패턴을 수치로 바꾸어 문자열의 비교를 수치

비교로 대신한다

• 문자열 패턴 Î 수치화

– 가능한 문자 집합 ∑의 크기에 따라 진수가 결정된다. – 예: ∑ = {a, b, c, d, e} • |∑| = 5 • a, b, c, d, e를 각각 0, 1, 2, 3, 4에 대응시킨다 • 문자열 “eeaab”를 수치화한 a1= 4*54+4*53+0*52+0*51+1*50 = 3001 – 이렇게 매번 a1, a2를 계산해가며 비교한다면 총 수행시간은 Θ(mn) 임 • ai 한 번 계산은Θ(m) 이 들고, • 계산해야 할 의 ai총 수는n-m+1 이기 때문 - 14 - 숙명여대 멀티미디어과학과 IT COOKBOOK IT COOKBOOK

문자열

Î 수치화 작업의 부담

• 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은 반복 사용되므로 미리 한번만 계산해 두면 된다

(8)

- 15 - 숙명여대 멀티미디어과학과 a c e b b c e e a a b c e e d b e e a a b p = 4*54 + 4*53+ 0*52+ 0*51+ 1 = 3001 a1=0*54+2*53+4*52+1*51+1 = 356 a2= 5(a1-0*54)+2 = 1782 a c e b b c e e a a b c e e d b a3=5(a2-2*54)+4 = 2664 a c e b b c e e a a b c e e d b

P[ ] A[ ] a7=5(a6-2*54)+1 = 3001 a c e b b c e e a a b c e e d b

수치화를 이용한 매칭의 예

IT COOKBOOK IT COOKBOOK

수치화를 이용해 매칭을 체크하는 알고리즘

basicRabinKarp(A, P, d) { ▷n : 배열 A[ ]의 길이, m : 배열 P[ ]의 길이 p = 0; a1= 0; for i ← 1 to m { ▷ 패턴P[ ]의 수치값과 a1계산 p ← dp + P[i]; a1da1 + 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] 자리에서 매칭이 되었음을 알린다; }

}

(9)

- 17 - 숙명여대 멀티미디어과학과

기본 라빈

-카프 알고리즘의 문제점

• 문자 집합 Σ와 m의 크기에 따라 a

i

가 매우 커질 수 있다.

– 심하면 프로그래밍 언어의 변수에 저장이 불가능할 수도… – 오버플로우 발생이 가능함.

• 해결책

– 나머지 연산modulo을 사용하여ai의 크기를 제한한다. – bi= aimod q – 여기서 q는 충분히 큰 소수로 잡되, dq가 레지스터에 수용될 수 있도록 잡는다

– 이렇게 하면 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사용

– bi의 크기는 모듈로 연산으로 인해q 미만으로 제한됨 - 18 - 숙명여대 멀티미디어과학과 IT COOKBOOK IT COOKBOOK a c e b b c e e a a b c e e d b e e a a b p = (4*54 + 4*53+ 0*52+ 0*51+ 1) mod 113 = 63 a1= (0*54+2*53+4*52+1*51+1) mod 113 = 17

a2= (5(a1-0*(54 mod 113))+2) mod 113 = 87

a c e b b c e e a a b c e e d b

a3= (5(a2-2*(54 mod 113))+4) mod 113 = 65

a c e b b c e e a a b c e e d b

P[ ]

A[ ]

a7= (5(a6-2*(54mod 113))+1) mod 113 = 63

a c e b b c e e a a b c e e d b

(10)

- 19 - 숙명여대 멀티미디어과학과

라빈

-카프 알고리즘 최종 버전

RabinKarp(A, P, d, q) { ▷n : 배열 A[ ]의 길이, m : 배열 P[ ]의 길이 p = 0; b1= 0; for i ← 1 to m { ▷ 패턴P[ ]의 수치값과 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] 자리에서 매칭이 되었음을 알린다; } } 9 평균 수행시간: Θ(n) IT COOKBOOK IT COOKBOOK

KMP

Knuth-Morris-Pratt

알고리즘

• 오토마타를 이용한 매칭과 동기가 유사

• 공통점

– 매칭에 실패했을 때 돌아갈 상태를 준비해둔다 – 오토마타를 이용한 매칭보다 준비 작업이 단순하다 . . . a b c d a b c d . . . . . a b c d a b c w z a b c d a b c w z A[ ] P[ ]

(11)

- 21 - 숙명여대 멀티미디어과학과 a b c d a b c w z 0 1 1 1 1 2 3 4 1 1 1 2 3 4 5 6 7 8 π[8] = 4 9 1 2 3 4 5 6 7 8 9 10 P[ ] π[ ] a b c d a b c w z

매칭이 실패했을 때 돌아갈 곳 준비 작업

텍스트에서abcdabc까지는 매치되고, w에서 실패한 상황 패턴의 맨앞의abc와 실패 직전의 abc는 동일함을 이용할 수 있다 실패한 텍스트 문자와P[4]를 비교한다 패턴의 각 위치에 대해 매칭에 실패했을 때 돌아갈 곳을 준비해 둔다 - 22 - 숙명여대 멀티미디어과학과 IT COOKBOOK IT COOKBOOK

KMP 알고리즘

KMP(A[ ], P[ ]) { preprocessing(P); i ← 1; ▷ 본문 문자열 포인터 j ← 1; ▷ 패턴 문자열 포인터 ▷n: 배열 A[ ]의 길이, m: 배열 P[ ]의 길이 while(i ≤ n) { if(j = 0 orA[i] = P[j]) then{ i++; j++; } else j ← π [j]; if(j = m+1) then { A[i-m]에서 매치되었음을 알림; j ← π [j]; } } } 9수행시간: Θ(n)

(12)

- 23 - 숙명여대 멀티미디어과학과

준비 작업

preprocessing(P) { i ← 1; ▷ 본문 문자열 포인터 k ← 1; ▷ 패턴 문자열 포인터 while(j ≤ m) { if(k = 0 orA[j] = P[k]) then{ j++; k++; π [j] ← k; } else k ← π [k]; if(j = m+1) then { A[i-m]에서 매치되었음을 알림; j ← π [j]; } } 9수행시간: Θ(m) IT COOKBOOK IT COOKBOOK

보이어

-무어

Boyer-Moore

알고리즘

• 앞의 매칭 알고리즘들의 공통점

– 텍스트 문자열의 문자를 적어도 한번씩 훑는다 – 따라서 최선의 경우에도 Ω(n)

• 보이어-무어 알고리즘은 텍스트 문자를 다 보지

않아도 된다

– 발상의 전환: 패턴의 오른쪽부터 비교한다

(13)

- 25 - 숙명여대 멀티미디어과학과 . . . b t i g e r . . t i g e r t i g e r 다섯칸 한꺼번에 점프! A[ ] P[ ]

Motivation

상황: 텍스트의 b와 패턴의 r을 비교하여 실패했다 9 관찰: 패턴에 문자 b가 없으므로 패턴이 텍스트의b를 통째로 뛰어넘을 수 있다 - 26 - 숙명여대 멀티미디어과학과 IT COOKBOOK IT COOKBOOK . . . t i g e r . . . . t i g e r t i g e r 세칸 한꺼번에 점프! A[ ] P[ ] 상황: 텍스트의 i와 패턴의 r을 비교하여 실패했다 9 관찰: 패턴에서 i가 r의 3번째 왼쪽에 나타나므로 패턴이3칸을 통째로 움직일 수 있다

(14)

- 27 - 숙명여대 멀티미디어과학과 오른쪽 끝문자 t i g e r 기타 jump 4 3 2 1 5 5 오른쪽 끝문자 r a t i o n a l 기타 jump 7 6 5 4 3 2 1 8 8 오른쪽 끝문자 r t i o n a l 기타 jump 7 5 4 3 2 1 8 8 패턴 “tiger”에 대한 점프 정보 패턴 “rational”에 대한 점프 정보

점프 정보 준비

IT COOKBOOK IT COOKBOOK

보이어

-무어-호스풀 알고리즘

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]]; } } 9최악의 경우 수행시간: Θ(mn) 9입력에 따라 다르지만 일반적으로 Θ(n)보다 시간이 덜 든다

(15)

- 29 - 숙명여대 멀티미디어과학과 . . . 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 4칸 점프 선택! 불일치문자 휴리스틱 일치접미부 휴리스틱

불일치문자 휴리스틱과 일치접미부 휴리스틱

- 30 - 숙명여대 멀티미디어과학과 IT COOKBOOK IT COOKBOOK . . . a a l e r . . . . r a t i o n a l 7칸 점프! -1칸 점프! . . . a a l e r . . . . 7칸 점프 선택! r a t i o n a l r a t i o n a l r a t i o n a l 불일치문자 휴리스틱 일치접미부 휴리스틱

(16)

- 31 - 한빛미디어㈜

Thank you

참조

관련 문서

 각자의 문제해결 방식이 다를 뿐 기본적으로 능력에 우열이 있는 것이 아니라는 입장.  어떤 사람은 유능하고 또 어떤 사람은 무능해

LISTBOX 리스트박스 윈도우 (문자열 목록을 가지며 선택된 문자열 표시) RichEdit 리치에디트 윈도우 (에디트 윈도우 보다 풍부한 편집기능 보유) SCROLLBAR

어려움을 겪는 지구천 이웃을 위해 어떤 마음을 지녀야 하는지 생각해 봅시다... 코이카는 경제적으로 어려움을 겪고 있는 나라에

폐기허증 面色㿠白 폐기쇠절증 面色㿠白 신기허증 面色㿠白 신기불고증 面色㿠白.

학교는 불평등한 경제구조와 관련되어 있는 특정 유형의 문화자본에 정당성을 부여 한다. 현재 미국 학교에서 가장 중요한 것으로 간주하 고 확산시키려는 지식은 '

 왼쪽 마우스를 클릭하면 출력하던 것이 멈췄을 때, WM_LBUTTONDOWN 메시지 처 리를 하는 곳으로 메시지 제어권을 보내주므로

- 만약 a와 c가 양이면 지수함수의 형태는 [그림 10.2]와 유사하지만 a와 c가 음이면 지수함수의 graph는..

교육과정사회학은 절대적인 지식이라 여겼던 학교교육과정을 비판 적으로 검토하면서 어떤 집단에 의해, 어떤 기제를 통해 취사선택 되 는가를 밝히고자