스트링 처리 알고리즘. 2 목차 스트링 탐색 알고리즘 – 직선적 알고리즘 –KMP 알고리즘 – 보이어 - 무어 알고리즘 – 라빈 - 카프 알고리즘 패턴 매칭 알고리즘 화일 압축 알고리즘 – 런 - 길이 인코딩 – 가변 - 길이 인코딩 암호화 알고리즘 – 단순한 기법 –

Presentation on theme: "스트링 처리 알고리즘. 2 목차 스트링 탐색 알고리즘 – 직선적 알고리즘 –KMP 알고리즘 – 보이어 - 무어 알고리즘 – 라빈 - 카프 알고리즘 패턴 매칭 알고리즘 화일 압축 알고리즘 – 런 - 길이 인코딩 – 가변 - 길이 인코딩 암호화 알고리즘 – 단순한 기법 –"— Presentation transcript:

1 스트링 처리 알고리즘

2 2 목차 스트링 탐색 알고리즘 – 직선적 알고리즘 –KMP 알고리즘 – 보이어 - 무어 알고리즘 – 라빈 - 카프 알고리즘 패턴 매칭 알고리즘 화일 압축 알고리즘 – 런 - 길이 인코딩 – 가변 - 길이 인코딩 암호화 알고리즘 – 단순한 기법 – 공개 키 암호화 시스템

3 3 스트링 탐색 알고리즘 문서 작성 시 – 텍스트 (text) : 문서, t[N] – 패턴 (pattern) : 탐색할 스트링, p[M] – 스트링 (string) 문자가 연속적으로 나열된 것 텍스트 (text) 스트링 이진 (binary) 스트링 스트링 탐색 알고리즘의 설계 목표 – 필연적으로 잘못된 시작 (false start) 발생 불일치가 발생한 위치까지 비교한 0 개 이상의 문자 – 잘못된 시작의 횟수와 길이를 줄이는 것 스트링 탐색 알고리즘의 응용 – 문서처리, 패턴인식, 음성인식, DNA 염기서열 분석

4 4 직선적 알고리즘 한 글자 또는 한 비트씩 오른쪽으로 진행 텍스트의 처음부터 끝까지 모두 비교하며 탐색하는 알고리즘 시간 복잡도 – 최악의 경우 시간 복잡도는 텍스트의 모든 위치에서 패턴을 비교해 야 하므로 O(MN) 이 됨 BruteForce(p[], t[]) M ← 패턴의 길이 ; N ← 텍스트의 길이 ; for (i←0, j←0; j < M and i < N; i←i+1, j←j+1) do if (t[i] ≠ p[j]) then { i ← i – j; j ← -1; } if (j = M) then return i - M; else return i; end ButeForce()

5 5 직선적 스트링 탐색 과정 1001110100101000101001110 10100111 10100111 10100111 10100111 10100111 10100111 10100111 10100111 10100111 10100111 10100111 10100111 10100111 10100111 10100111 10100111 1001110100101000101001110

6 6 0123456789111213141516171819202122232425 ababababcababababcaabbaba abababca 0123456789111213141516171819202122232425

7 7 KMP 알고리즘 (1) KMP : Knuth, Morris and Pratt 불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행 패턴을 전처리하여 배열 next[M] 을 구해서 잘못된 시작을 최소화함 –next[M] : 불일치가 발생했을 경우 이동할 다음 위치 시간 복잡도 : O(M+N)

8 8 KMP 알고리즘 (2) KMP(p[], t[]) M ← 패턴의 길이 ; N ← 텍스트의 길이 ; InitNext(p); for (i ← 0, j ← 0; j < M and i < N; i ← i + 1, j ← j + 1) do { while ((j ≥ 0) and (t[i] ≠ p[j])) do j ← next[j]; } if (j = M) then return i - M; else return i; end KMP() InitNext(p[])// 재 시작 위치 알고리즘 M ← 패턴의 길이 ; for (i ← 0, j ← -1; i < M; i ← i + 1, j ← j + 1) do { next[i] ← j; while ((j ≥ 0) and (p[i] ≠ p[j])) do j ← next[j]; } end InitNext()

9 9 KMP 알고리즘 탐색 과정 ⓞ①②③④⑤⑥⑦⑧⑨ⓞ①②③④⑤⑥⑦⑧⑨ⓞ①②③④ 1001110100101000101001110 10100111 10100111 10100111 10100111 10100111 10100111 10100111 10100111 1001110100101000101001110 i012345678910111213141516…2324 j012001010123456123450 0…78 ⓞ①②③④⑤⑥⑦ 0012011 next

10 10 재 시작 위치 (1) - next[j] : 아래쪽 패턴의 왼쪽에 위쪽 패턴과 동일한 문자의 개수 - next[0] = -1 - j=1 에서 시작 - 아래쪽 패턴과 위쪽 패턴이 일치하는 동안에는 아래쪽 패턴을 이동하지 않고 - 아래쪽 패턴과 위쪽 패턴이 일치하지 않으면 아래쪽 패턴의 첫 문자가 위쪽 패턴과 일치하는 위치까지 아래쪽 패턴을 오른쪽으로 이동 10100111 에 대한 재 시작 위치

11 11 재 시작 위치 (2) abababca 에 대한 재 시작 위치

12 12 패턴이 내장된 KMP 알고리즘 (1) KMP(t[]) i ← -1; sm : i ← i + 1; s0 : if (t[i] ≠ '1') then goto sm; i ← i + 1; s1 : if (t[i] ≠ '0') then goto s0; i ← i + 1; s2 : if (t[i] ≠ '1') then goto s0; i ← i + 1; s3 : if (t[i] ≠ '0') then goto s1; i ← i + 1; s4 : if (t[i] ≠ '0') then goto s2; i ← i + 1; s5 : if (t[i] ≠ '1') then goto s0; i ← i + 1; s6 : if (t[i] ≠ '1') then goto s1; i ← i + 1; s7 : if (t[i] ≠ '1') then goto s1; i ← i + 1; return i-8; end KMP()

13 13 패턴이 내장된 KMP 알고리즘 (2) 유한 상태 장치 (finite state machine: FSM) – 상태 (state; 원으로 표시 ) – 전이 (transition; 선으로 표시 ) 일치 전이 (match transition; 실선으로 표시 ) – 오른쪽으로 이동 불일치 전이 (non-match transition; 점선으로 표시 ) – 왼쪽으로 이동 – 시작점 ( 왼쪽 끝의 사각형 ) – 종료점 ( 오른쪽 끝의 사각형 )

14 패턴이 내장된 KMP 알고리즘 (3) KMP 알고리즘을 위한 유한 상태 장치 s0s1s2s3s4s5s6s7 10100111 sm P Ⓞ Ⓞ Ⓞ ① ① ① ② ⓞ①②③④⑤⑥⑦ 0012011 next ※ next 와 일치

15 15 유한 상태 장치 예 (1) 개선된 알고리즘 –pattern matching table 사용 ( 예 ) 패턴 P = ‘ aaba ’ 인 경우 a b x Q0Q1Q2Q3Q0Q1Q2Q3 Q 1 Q 0 Q 0 Q 2 Q 0 Q 0 Q 2 Q 3 Q 0 P Q 0 Q 0 pattern matching table Q0Q0Q0Q0 Q1Q1Q1Q1 Q2Q2Q2Q2 Q3Q3Q3Q3P aaba b b a b pattern matching graph sksk TkTk

16 16 유한 상태 장치 예 (2) ( 예 ) 패턴 P = ‘ aaabb ’ 인 경우 a b Q0Q1Q2Q3Q4Q0Q1Q2Q3Q4 Q 1 Q 0 Q 2 Q 0 Q 3 Q 0 Q 3 Q 4 Q 1 P pattern matching table pattern matching graph Q0Q0Q0Q0 Q1Q1Q1Q1 Q2Q2Q2Q2 Q3Q3Q3Q3P aaab b b a b Q4Q4Q4Q4 b a sksk TkTk

17 17 유한 상태 장치 예 (3) ( 예 ) 패턴 P = ‘ ababab ’ 인 경우 a b Q0Q1Q2Q3Q4Q5Q0Q1Q2Q3Q4Q5 Q 1 Q 0 Q 1 Q 2 Q 3 Q 0 Q 1 Q 4 Q 5 Q 0 Q 4 P pattern matching table pattern matching graph Q0Q0Q0Q0 Q1Q1Q1Q1 Q2Q2Q2Q2 Q3Q3Q3Q3 P abab b b a b Q4Q4Q4Q4 a a Q5Q5Q5Q5 b a sksk TkTk

18 개선된 유한 상태 장치 (1) s0s1s2s3s4s5s6s7 10100111 smP 개선된 유한 상태 장치 Ⓞ -①-① -①-① Ⓞ ① ① ② ⓞ①②③④⑤⑥⑦ 0 02 11 next ※ next 와 일치

19 19 개선된 유한 상태 장치 (2) InitNext 알고리즘의 next[i] ← j; 변경 if (p[i] = p[j]) then next[i] ← next[j]; else next[i] ← j InitNext(p[]) M ← 패턴의 길이 ; next[0] ← -1; for (i ← 1, j ← 0; i < M; i ← i + 1, j ← j + 1) do { if (p[i] = p[j]) then next[i] ← next[j]; else next[i] ← j while ((j ≥ 0) and (p[i] ≠ p[j])) do j ← next[j]; } end InitNext()

20 20 개선된 유한 상태 장치 (3) ⓞ①②③④⑤⑥⑦⑧⑨ⓞ①②③④⑤⑥⑦⑧⑨ⓞ①②③④ 1001110100101000101001110 10100111 10100111 10100111 10100111 10100111 10100111 ⓞ①②③④⑤⑥⑦ 0 02 11 next 개선된 유한 상태 장치를 이용한 KMP 알고리즘 수행 과정 시간 복잡도 : O(M+N) M+N 번 이상의 비교를 하지 않음

21 21 개선전 KMP 알고리즘 탐색 과정 ⓞ①②③④⑤⑥⑦⑧⑨ⓞ①②③④⑤⑥⑦⑧⑨ⓞ①②③④ 1001110100101000101001110 10100111 10100111 10100111 10100111 10100111 10100111 10100111 10100111 1001110100101000101001110 ⓞ①②③④⑤⑥⑦ 0012011 next

22 22 개선된 유한 상태 장치 (4) 개선된 유한 상태 장치를 이용한 KMP 알고리즘 수행 과정 –abababca J1234567 next[j]00 04

23 23 개선전 재 시작 위치 abababca 에 대한 재 시작 위치

24 문자열을 왼쪽부터 패턴의 길이 만큼 조사 범위를 정한다 패턴과 텍스트의 조사 범위를 오른쪽 끝에서 왼쪽으로 조사 일치하지 않는 부분과의 비교를 생략하기 위해 조사 범위를 이동 패턴의 문자를 중심으로 조사 범위를 결정하기 위해 이동 시킬 자리수 결정 패턴이 길 때 효과적 24 보이어 - 무어 (Boyer-Moore) 알고리즘

25 25 보이어 - 무어 (Boyer-Moore) 알고리즘  오른쪽에서 왼쪽으로 스트링 탐색을 진행  불일치 문자 방책 (mismatched character heuristic) 사용  텍스트에서 불일치가 발생한 문자가 패턴의 문자와 일치하도록 패 턴을 오른쪽으로 이동  일치 접미부 방책 (good suffix heuristic) 사용  패턴에서 불일치가 발생한 문자의 오른쪽에 있는 최대 접미부가 일 치하도록 패턴을 오른쪽을 이동하는 것  두 방법 중 패턴을 우측으로 이동하는 거리가 더 긴 것 선택  M+N 번 이상 비교하지 않음

26 26 불일치 문자 방책과 일치 접미부 방책

27 27 불일치 문자 방책 알고리즘 (1) MisChar(p[], t[]) M ← 패턴의 길이 ; N ← 텍스트의 길이 ; InitSkip(p); for (i ← M-1, j ← M-1; j ≥ 0; i ← i - 1, j ← j - 1) { while (t[i] ≠ p[j]) do { k ← skip[index(t[i])]; if (M-j > k) then i ← i + M - j;// 이동거리가 긴 것 선택 else i ← i + k; if (i ≥ N ) then return N;// 매칭 실패 j ← M - 1; } } return i+1;// 매칭 성공 end MisChar()

28 28 불일치 문자 방책 알고리즘 (2) InitSkip() : skip 배열 생성 텍스트 상에 나타날 수 있는 모든 문자에 대해 이동량 계산 패턴이 ATION 일 때의 skip 배열 void InitSkip(char *p) { int i, j, M = strlen(p); for (i = 0; i < NUM; i++) // NUM=27 ( 영어 알파벳 대문자의 개수 ) skip[i] = M; for (i = 0; i < M; i++) skip[index(p[i])] = M - i - 1; } 알파벳의 순서 수 리턴 함수 공백은 0, a 는 1, …, z 는 26 5 [0] 공백 …[20]……[15][14]…[9]…[2][1] …T……ON…I…BA 문자 53551052554Skip

29 29 불일치 문자 방책 알고리즘 (3) 불일치 문자 방책을 사용한 보이어 - 무어 스트링 탐색 과정 5 [0] 공백 …[20]……[15][14]…[9]…[2][1] …T……ON…I…BA 문자 53551052554Skip

30 30 불일치 문자 방책 알고리즘 (4) 알고리즘의 수행 text : “old soldiers never die, they just fade away.” pattern : never Oldsoldiersneverdie,… never never i=12 일 때 종료  13 return never never never 012345678910111213141516171819202122… n=44, m=5 ↑ ↑ ↑ ↑ ↑ 문자공백 ab…e…n…r…v… [0][1][2]…[5]…[14]…[18]…[22]… Skip555515450525

31 31 라빈 - 카프 알고리즘  스트링을 숫자값으로 바꾼 다음 해시 값을 계산하여 매칭 하는 알고리즘  최악의 시간 복잡도는 O(MN) 평균적으로는 선형에 가까운 빠른 속도를 가지는 알고리즘  이론적인 배경 첫 번째 M 자리의 나머지를 구한 다음부터는 한 자리씩만 추가하 면서 간단한 계산으로 나머지를 구할 수 있으므로 빠른 시간에 스 트링 탐색을 수행

32 32 호너의 방법 패턴 P[M] 에 대한 10 진수 p 의 계산 과정 패턴 P[M] = 31415 라고 할 때, p 를 구하는 과정 이 성질은 다른 연산에도 적용될 수 있음

33 33 호너의 방법 응용 mod 연산의 성질 (a  b) mod q = ((a mod q) (b mod q)) mod q = ((a mod q)  b) mod q = (a  (b mod q)) mod q 31415 를 13 으로 나눈 나머지 (=7) 31415 = (((3 * 10 + 1) * 10 + 4) * 10 + 1) * 10 + 5 31 mod 13 = 5 54 mod 13 = 2 21 mod 13 = 8 85 mod 13 = 7

34 34 계산 예 (1) 314152 텍스트 : 7 8 d = 10, q = 13, m = 5, dM = 10 4 mod 13 = 3 14152 mod 13 = ((31415 - 3  10 4 )  10 + 2) mod 13 = ((7 - 3  3)  10 + 2) mod 13 = ((7 + 10  13 - 3  3)  10 + 2) mod 13 = (11  10 + 2) mod 13 = 8 31415 mod 13 = 7 128 mod 13 = 11 112 mod 13 = 8 음수 값에 대한 mod 연 산 방지

35 35 계산 예 (2) 2359023141526739921 텍스트 : 패턴 : mod 13  7 spurious hit 이 발생할 수 있음  q 를 충분히 큰 수로 해주면 어느 정도 예방할 수 있다 31415 893 11 017845 1011 79

36 36 라빈 - 카프 알고리즘 RabinKarp(p[], t[]) dM ← 1; h1 ← 0; h2 ← 0; M ← 패턴의 길이 ; N ← 텍스트의 길이 ; for (i ← 1; i < M; i ← i + 1) do dM ← (d*dM) mod q; for (i ← 0; i < M; i ← i + 1) do { h1 ← (h1 * d + index(p[i])) mod q; h2 ← (h2 * d + index(t[i])) mod q; } for (i ← 0; h1 ≠ h2; i ← i + 1) do { h2 ← (h2 + d * q - index(t[i]) * dM) mod q; h2 ← (h2 * d + index(t[i+M])) mod q; if (i > N-M) then return N; } return i; end RabinKarp()

37 37 패턴 매칭 알고리즘 패턴 매칭 (pattern matching) – 텍스트 스트링에서 원하는 문자 패턴을 찾아 내는 것 – 패턴의 표현 ① 접합 (concatenation) – 패턴에서 인접해 있는 두 문자가 텍스트에서 나타나면 매치 –AB : A 다음에 B 가 온다 ② 논리합 (or) – 두 개의 문자 중 하나가 텍스트에 나타나면 매치 –C(AC+B)D : CACD 또는 CBD –(A+C)((B+C)D) :ABD, CBD, ACD, CCD ③ 폐포 (closure) – 특정한 문자가 0 개 이상 나타나면 매치 –AB* : A 다음에 B 가 0 개 이상 온다 –(AB)* : AB 가 번갈아 0 개 이상 온다

38 38 정규식 (regular expression)  패턴을 표현하기 위해 세 가지 기본 연산으로 구성된 심볼 들의 스트링  심볼 (symbol) 1.* : 괄호 안에 있는 문자들이 0 번 이상 나타남 2.? : 어떤 문자와도 매치됨 (예)(예) ?*(ie+ei)?* : ie 또는 ei 를 가지고 있는 모든 단어 (1+01)*(0+1) : 0 이 연속적으로 두 개 이상 오지 않는 이진 스트링

39 39 패턴 매칭 장치 패턴 매칭 장치 (pattern matching machine) – 패턴 매칭에 사용되는 장치 패턴 – 결정적 (deterministic) 장치 각각의 상태 전이가 다음 입력 문자에 의해 완전하게 결정되는 것 ( 예 ) KMP 알고리즘을 위한 유한 상태 장치 – 비결정적 (nondeterministic) 장치 패턴을 매치하기 위해 하나 이상의 방법이 있을 경우 장치가 올바 른 것을 찾아 나가는 것 텍스트 스트링에서 (A*B+AC)D 와 같은 정규식을 찾는 경우 사용 되며, 유일한 시작 상태와 종료 상태를 가진다.

40 40 패턴 매칭 구성 방법 패턴 매칭 구성 장치 논리합 접합 폐포

41 41 패턴 매칭 장치 예 (A*B+AC)D 를 위한 비결정적 패턴 매칭 장치 패턴 매칭 장치의 배열 표현 [0][1][2][3][4][5][6][7][8][9] ch A B ACD next15234867890 next25214827890

42 42 패턴 매칭 알고리즘 구현 패턴 매칭 장치를 구현 – 모든 가능한 매치를 체계적으로 조사 – 장치를 구현하는데 가장 적합한 자료구조 데크 (deque: double-ended queue) 를 사용 – 스택과 큐의 특징을 조합 – 양방향에서 항목을 추가하는 것이 가능 – 입력은 양방향에서 가능 – 삭제는 데크의 처음에서만 가능한 출력 - 제한 데크 (output- restricted deque) 로 사용 N 문자로 이루어진 텍스트 스트링에서 M- 상태 장치가 패턴을 찾는 것 은 최악의 경우에도 NM 번 이하의 상태 전이만이 필요

43 43 동작 과정 scan 을 만남  입력 스트링에 대한 포인터를 다음 문자로 이동 문자가 매치됨  새로운 상태를 데크의 끝에 삽입 (insertLast) 상태가 비어 있음  두 개의 가능한 상태를 데크의 처음에 삽입 (insertFirst) 그 외의 경우 : 아무 동작도 하지 않음 종료 조건 – 입력의 끝까지 갔을 때 ( 매치되지 않음 ) – 상태 0 을 만남 ( 매치됨 ) – 데크에 scan 마크 하나만 남음 ( 매치되지 않음 )

44 int match(char *t) { int n1, n2; Deque dq(100); int j=0, N=strlen(t), state=next1[0]; dq.insertLast(scan); while (state) { // state 가 0 이면 종료 ( 매치성공 ), j-1 return if (state == scan) { // scan 만남 j++; if (dq.isEmpty()) dq.insertFirst(next1[0]); dq.insertLast(scan); } else if (ch[state]==t[j]) dq.insertLast(next1[state]) // 문자매치 else if (ch[state] == ‘ ‘) { // 비어있음 n1 = next1[state]; n2 = next2[state]; dq.inserFirst(n1); if (n1 != n2) dq.inserFirst(n2); } if (dq.isEmpty()) return j; if (j>N) return 0;// 텍스트 끝 state = dq.deleteFirst(); } return j-1; } 44

45 45 패턴 매칭 알고리즘 수행 예 AAABD 식별 과정 ( 데크에서 처리과정 ) First Last j=0 j=1 j=2 j=3 j=4 j=5 ++ 6 2 + 6 2 + 3 6 1 + 3 6 1 + 2 3 6 + 2 3 6 + 2 6 + 2 6 + 7 + 2 7 + 2 + 2 7 + 2 7 3 + 1 7 3 + 1 7 2 3 7 + 2 3 7 + 2 7 + 2 7 + 2 + 2 + + 2 + 2 + 1 3 + 1 3 2 3 + 2 3 + 2 + 2 + + 2 + 2 + 1 3 + 1 3 + 3 + 3 4 + 4 + + 4 + 4 + 8 + 8 9 + 9 + + 9 + 9 + 0 + A A A A B D ++ [0][1][2][3][4][5][6][7][8][9] ch A B ACD next15234867890 next25214827890