이 내용은 시간복잡도와 Big-O 를 알고 있어야 이해할 수 있다.
KMP Algorithm : 문자열에서 특정 패턴 문자열을 찾는 방법이다.
1. 일반적인 문자열에서 패턴 문자열 찾기
↓ ↓ ↓
| String | A | B | C | F | A | B | D | C |
| Pattern | A | B | D |
↓
| String | A | B | C | F | A | B | D | C |
| Pattern | A | B | D |
↓
| String | A | B | C | F | A | B | D | C |
| Pattern | A | B | D |
↓ ↓ ↓
| String | A | B | C | F | A | B | D | C |
| Pattern | A | B | D |
위에 있는 문자열은 전체 문자열이다. --> String
아래에 있는 문자열은 우리가 찾고자 하는 패턴 문자열이다. --> Pattern
String 의 첫 글자부터 Pattern 문자열과 비교해서 같으면 다음 글자를 비교하고 ... 이를 반복한다.
만약 다르다면 String 의 다음 글자부터 다시 비교한다.
시간 복잡도를 계산해 본다면
1. String 의 글자 수 인 m 번 만큼 반복한다.
2. 각각의 경우에 Pattern 의 글자 수 인 n 까지 일치하는지 확인한다.
따라서 O(mn) 이 나온다.
이 시간 복잡도를 줄이기 위해 KMP Algorithms 이 만들어 졌다.
2. 시간 복잡도를 줄이는 메커니즘
↓ ↓ ↓
| String | A | B | C | F | A | B | D | C |
| Pattern | A | B | D |
↓
| String | A | B | C | F | A | B | D | C |
| Pattern | A | B | C |
위의 예시에서 A B 두 글자가 일치하고 D 글자가 불일치 한 다음에 다시 비교를 할 때 String 의 두번째 글자부터 비교를 시작했다. 즉 String 의 비교 화살표는 C까지 갔다가 다시 B로 되돌아 오는 상황이 된다.
만약 String 의 비교 화살표가 뒤로 되돌아 오지 않고 한 방향으로 쭉 가면 시간 복잡도는 줄어들 것이다.( O(m)+O(n) )
a. 시간 복잡도 줄이기
↓ ↓ ↓
| String | A | B | C | F | A | B | D | C |
| Pattern | A | B | D |
↓
| String | A | B | C | F | A | B | D | C |
| Pattern | A | B | D |
우리는 첫번째 비교로 앞 두글자 A B 는 일치하고 C 부터 틀리다는 것을 알았다. 그렇다면 그냥 바로 틀렸던 글자인 C 부터 다시 비교하면 안될까? 그렇게 해도 된다면 시간 복잡도는 위에서 말한 이유처럼 줄어들게 된다.
b. 고려해야 하는 것
↓ ↓ ↓ ↓ ↓ ↓
| String | A | B | C | A | B | C | A | B | D |
| Pattern | A | B | C | A | B | D |
↓
| String | A | B | C | A | B | C | A | B | D |
| Pattern | A | B | C | A |
위 처럼 바로 넘어갔을 때 건너 뛰는 A B 가 패턴에 일치되는 문자열의 앞부분일 수 있다. 따라서 함부로 불일치하는 곳 까지 넘어가면 안된다.
c. 해결방법
↓ ↓ ↓ ↓ ↓ ↓
| String | A | B | C | A | B | C | A | B | D |
| Pattern | A | B | C | A | B | D |
X X ↓
| String | A | B | C | A | B | C | A | B | D |
| Pattern | A | B | C | A | B | D |
만약 우리가 Pattern 의 앞부분이 String 의 건너뛰는 부분과 일치하는 곳을 안다면 그 다음 부분부터 비교를 진행하면 된다.
우리가 미리 Pattern 의 문자열을 분석하여 앞부분 글자와 겹치는 부분을 안다면 시간 복잡도가 줄어들 것이다.
d. 정리
위의 생각들을 정리하자면
1. 특정 패턴 문자열에서 불일치가 발생했을 때 A B C A B C D
2. 패턴 문자열의 앞부분(prefix) 과 일치하는 부분(suffix) 를 안다면 A B C A B C D
3. 일치하는 부분 다음 글자부터 비교를 하면 된다 A B C A B C D
4. 이렇게 된다면 String 의 비교 화살표는 뒤로 돌아오지 않고 한 방향으로 쭉 비교를 진행한다.
3. KMP Algorithm 구현하기
위에서 다룬 내용을 다시 한 번 보고 가자.
1. 우리는 문자열에서 특정 패턴 문자열을 찾으려고 한다.
2. 일치된 문자열을 건너 뛰어 시간복잡도를 줄이려고 하는데 문자열을 건너 뛸 때 생기는 문제점이 있다.
3. 이를 해결하기 위해 패턴 문자열에서 미리 앞부분에 겹치는 글자가 '있는지, 얼마나 있는지' 를 미리 구하려고 한다.
1. 패턴 문자열에서 미리 정보를 구해놓기
| Pattern | A | B | C | A | B | A | B | C | |
| T[n] | -1 | -1 | -1 | 0 | 1 | 0 | 1 | 2 |
위는 패턴 문자열과 T 인덱스이다. T 인덱스는 현재 패턴 문자열에서 앞 글자와 지금 글자가 prefix 와 일치하는지에 대한 데이터를 담고 있다.
단순히 보았을때 처음 T 값이 0 이 된 부분을 보면 prefix 와 같기 때문에 T 값이 0 이 되었다.
다음 글자인 B 도 앞글자인 A가 prefix와 일치하고 B 또한 prefix 와 같기 때문에 T 값은 증가하여 1 이 된다.
즉 prefix 와 같은 글자라면 T 값은 0 이 아니고 연속적으로 같은 글자면 T 값은 1씩 증가하게 된다.
아래 다른 예시 몇 개를 본다면 대충 어떤 패턴인지 알 수 있을 것이다.
| Pattern | A | B | C | A | A | A | C | D | |
| T[n] | -1 | -1 | -1 | 0 | 0 | 0 | -1 | -1 |
| Pattern | A | B | A | C | A | B | B | C | |
| T[n] | -1 | -1 | 0 | -1 | 0 | 1 | -1 | -1 |
| Pattern | A | B | C | A | B | C | A | B | |
| T[n] | -1 | -1 | -1 | 0 | 1 | 2 | 3 | 4 |
2. 패턴 문자열에서 미리 정보 구하는 코드
void fail(char *pat) {
/* compute pattern's failure function */
int i, j, n = strlen(pat);
failure[0] = -1; // 첫번째 T=-1
for(j=1; j<n; j++) { // 두번째 글자부터 마지막 글자까지 비교
i = failure[j-1]; // 이 전 글자의 T 값이 앞 글자의 i 값
// i 가 양수고 이번 글자와 prefix 다음 글자가 다를 경우
while((i >= 0) && (pat[j] != pat[i + 1])) // i>=0 이라면 이 전 글자(들)이 일치한다는 거고 --> i 가 한번 거쳤는데도 양수면 현재 글자와 같은 글자가 앞 prefix 에 있다는 것?
i = failure[i]; // 이제 이번 글자와 prefix 를 비교
// 만약 일치하지 않으면
// 지금 현재 글자 전까지는 prefix 와 일치하니까
// 현재 글자와 prefix 다음 글자와 비교 반복
// 지금 현재 글자랑
if(pat[j] == pat[i+1]) // 이번 글자와 prefix 다음 글자 비교
failure[j] = i+1; // 일치하면 T 값을 하나씩 증가
else failure[j] = -1; // 다르면 T = -1
}
}
3. 미리 정보를 처리한 패턴 문자열과 문자열을 비교하는 함수
우리는 패턴 문자열에 앞부분에 겹치는 글자가 얼마나 있는지를 미리 구해놨습니다. ( T[n] )
이제 패턴 문자열과 문자열을 비교해봅시다.
| String | A | B | C | F | A | B | C | D | A | B | D |
| Pattern | A | B | C | D | A | B | D | ||||
| T[n] | -1 | -1 | -1 | -1 | 0 | 1 | -1 |
| String | A | B | C | F | A | B | C | D | A | B | D |
| Pattern | A | B | C | D | A | B | D | ||||
| T[n] | -1 | -1 | -1 | -1 | 0 | 1 | -1 |
위와 같은 경우 String 의 불일치한 F 부분 부터 Pattern 의 첫 부분인 A 부터 다시 비교를 시행합니다.
| String | A | B | C | D | A | B | F | A | C | B | D |
| Pattern | A | B | C | D | A | B | D | ||||
| T[n] | -1 | -1 | -1 | -1 | 0 | 1 | -1 |
| String | A | B | C | D | A | B | F | A | C | B | D |
| Pattern | A | B | C | D | A | B | D | ||||
| T[n] | -1 | -1 | -1 | -1 | 0 | 1 | -1 |
위와 같은 경우 String 의 불일치한 부분 F 부터 Pattern 의 세번째 부분인 C 부터 비교를 시행합니다. 앞 글자인 A B 는 prefix 와 일치하다는 것을 T[n] 을 통해 알 수 있기 때문입니다.
int pmatch(char *string, char *pat) {
/* Knuth-Morris-Pratt string matching algorithm */
int i=0, j=0;
int lens = strlen(string);
int lenp = strlen(pat);
// i 길이랑 j 길이 둘 중 하나 끝날 때 까지
while(i < lens && j < lenp) {
// string i 글자 pattern j 글자 비교
//같으면 비교화살표 둘 다 증가
if(string[i] == pat[j])
{ i++; j++; }
// 다르고 pattern 첫 글자면 String i 비교 화살표 증가
else if(j == 0)
i++;
// 다르고 pattern 비교화살표 가 첫 글자가 아니면 --> 전 글자가 prefix 와 같으면
// pattern 의 비교화살표는 이 전 T[]값 ( 겹치는 글자 수) + 1 --> 겹치는 글자 수 다음 글자
else
j = failure[j-1] + 1;
}
return ((j==lenp) ? (i-lenp) : -1);
}위 코드가 미리 정보를 처리한 Pattern 과 String 을 비교하는 코드입니다.
4. KMP Algorithm 의 시간복잡도
이제까지 일반적인 문자열에서 패턴 문자열 찾기 의 시간복잡도를 줄이기 위한 KMP Algorithm 을 살펴 보았다.
원래의 시간복잡도는 String 의 길이인 m, Pattern 의 길이인 n 으로 O(mn) 이었다.
KMP Algorithm 의 시간 복잡도는 다음과 같다.
Pattern 의 정보 처리 함수 : 비교 화살표가 항상 1씩 증가하면서 앞부분 글자와 같은지 비교한다. --> n 번 시행
문자열 비교 함수 : String 의 비교 화살표는 항상 1씩 증가하며 뒤로 되돌아가지 않는다. --> m 번 시행
따라서 시간 복잡도는O(m + n) 이다.
원래의 시간 복잡도 O(mn) 과 비교했을 때 상당히 효율적이다.
참고자료 : 서강대학교 소정민 교수님 수업자료
'수업정리 > 자료구조' 카테고리의 다른 글
| 시간 복잡도 이해하기 (0) | 2021.09.23 |
|---|
