KMP알고리즘
코드를 간단히 확인 후, 어떻게 next[]를 채우는지 알아보자.
우선은 어떻게 KMP에 접근할 것인지 표로 관찰해보고,
그 다음에는 코드로 익혀보도록 하자.
int KMP_Search(char *p, char *a)
{
int i, j, M, N;
M = strlen(p); N = strlen(a);
InitNext(p); //패턴(p)로 next[] 초기화하는 함수
for(i = 0, j = 0; j < M && i < N; i++, j++)
while(j >= 0 && a[i] != p[j])
j = next[j];
if(j == M) return(i-M);
else return(N);
}
InitNext(char *p)
{
int i, j, M;
M = strlen(p);
next[0] = -1;
for(i = 0,j = -1; i < M; i++, j++, next[i] = j)
while(j >= 0 && p[i] != p[j])
j = next[j];
}
비교할 문장(A): abcaababaababbaaa
패턴 예제: ababbaaa
여기서는, 비교할 문장(A)과 대조하는 것이 아니라, 패턴(ababbaaa)과 패턴(ababbaaa)을 비교한다.
위의 KMP알고리즘 코드를 살펴보면
next[0] = -1 로 나와있다. 따라서 next배열의 맨 처음은 -1로 시작한다.
next배열은, 패턴(ababbaaa)과 비교할 문장(A)를 비교할 때, 만약 패턴(ababbaaa)과 비교할 문장(A)중 다른 부분이 있다면, 다음 순서는 패턴의 어느 위치에서 시작할 것인지를 알려주는 것을 의미한다.
즉, 내가 틀리면 패턴의 어느 위치에서 다시 비교해? = next 배열의 역할인 것.
이렇게 대략적으로 next[]의 역할을 알아보았으니,
이제 next[]을 채워보자.
위에서 설명한 바와 같이, next[0] = -1로 채운다.
( 이해를 돕기 위해, 표에서 윗줄에 있는 패턴은 P라 하고, 표에서 아랫줄에 있는 패턴은 P' 이라고 하자.
단, 표의 윗줄에 있는 패턴 P는 이동하지 않는다. 표의 아랫줄에 있는 페턴 P'만 이동한다. )
이제부터 차근차근 시작해보자.
여기서는 코드 설명보다 직관적인 이해를 위해 그림으로 먼저 이해해보기로 한다.
패턴의 맨 처음 a는 next[0] = -1이기 때문에, 비교하지 않는다.
next[1]을 생각해보면,
b 와 a 는 일치하지 않는다. a 의 인덱스는 0 이므로 next[1] = 0을 넣는다.
그리고 b와 a가 불일치했기 때문에 next[2]를 구하기 위해 패턴(P')을 한 칸 이동시킨다.
여기서 점검해야하는 것은,
불일치한 경우
패턴(P)의 해당 위치 next[]를 채운 뒤, 패턴을 이동시키고 더이상 next[]를 수정하지 않는다는 점이다.
위에서 본 것처럼, 패턴을 이동하더라도 next[1] = -1로 다시 수정하지 않는다는 것.
여기서 본다면 당연한 것처럼 느껴지지만 하단의 설명에서 헷갈릴 수 있는 부분이니 반드시 짚고 넘어가야 한다.
패턴(P')을 옆으로 한 칸 밀었을 때, 첫 부분에서 P와 P'이 일치하는 부분이 있다.
앗 그런데 우연히도 또 일치하는 부분이 있다.
흠 그렇지만 a와b까지만 일치하고 그 다음은 일치하지 않는다는 것을 확인헀다.
따라서,패턴(P)의 a와 b 위치에 해당하는 next[]는, 패턴(P)와 패턴(P')가 일치하는 부분의 패턴(P')의 인덱스를 각각 넣어준다.
패턴(P')에서 a 의 인덱스는 0이고 b 의 인덱스는 1이기 때문에, next[2]와 next[3]에 각각 0과 1을 넣어준다.
그리고 궁금해지는 부분. 그러면 next[4]는?
아까 언급한 내용을 다시 떠올려보자.
불일치한 경우
패턴(P)의 해당 위치 next[]를 채운 뒤, 패턴을 이동시키고 더이상 next[]를 수정하지 않는다는 점.
그렇다면 불일치한 부분의 next[4]를 채워보자.
패턴(P')에서 a 의 인덱스는 2 이기 때문에
next[4] =2를 넣어준다.
그리고 패턴(P')을 한 칸 뒤로 이동시켜준다.
여기서 또 궁금한 부분이 생긴다.
next[4]까지 채웠다. 그런데 지금 한 칸 밀었으면 next[4]는 채워져있는데 어떻게 되는거지?
next[]가 채워져있는 부분은 그대로 두자. (수정하지 않는다.)
우리가 원칙적으로 해야할 일은, 패턴(P')의 인덱스가 0인 곳과 일치하는 부분의 패턴(P)를 만날때까지 한 칸씩 뒤로 밀어준다는 것. 그래서 P'의 첫 문자와 일치하지 않는다면 next[]에 0을 넣어준 것이었지만, 이미 next[4]가 채워져있기 때문에 우리는 원칙대로 한 칸을 밀어서 다음을 비교한다.
그런데, P의 b와 P'의 a가 불일치한다. 하지만 next4]는 채워져있기 때문에 다시 P'을 한 칸 밀어준다.
P[5]위치에 P'[0]을 위치시킨다.
이제 패턴(P)와 패턴(P')을 비교하면
a 와 a 는 일치하지만 a 와 b 가 불일치한다는 것을 알 수 있다.
next[5]위치에는, 패턴(P')의 a 에 해당하는 인덱스인 0,
next[6]위치에는, 패턴(P')의 b 에 해당하는 인덱스인 1을 채워준다.
즉, next[5]=0 , next[6]=1 을 채워준다.
그리고 패턴(P')을 한 칸 밀어준다.
그러면 패턴(P)의 와 패턴(P')가 일치하는 부분을 찾았다.
a 에 해당하는 패턴(P)의 인덱스가 6이므로 next[6]을 확인하면 next[6]=1로 이미 채워져있다.
따라서 이미 next[]가 채워져있는것은 수정하지 않고, a 다음을 확인한다.
a 와 b 가 불일치한다는 것을 확인했다.
next[6]은 이미 채워져있으므로, 불일치하는 부분인 next[7]을 채워주기 위해서는
패턴(P')의 b 인덱스에 해당하는 1을 next[7]에 넣어준다.
요약해보면,
1) next[0]=-1을 넣어주고(코드에 나온것처럼)
2) P[i]와 P'[0]을 지속적으로 비교한다. 만약 P'[0]에서부터 불일치 한다면 next[i]에 0을 넣어주고 한칸 씩 뒤로 밀어준다.
이미 next[i]가 채워져 있다면 다시 수정하지 않는다.
3) 만약 P[j]와 P'[0]이 일치한다면 next[j]=0을 넣고, 그리고 P[j+1]과 P'[1]을 비교한다. 단, 이미 next[i]가 채워져 있다면 다시 수정하지 않는다.
4) P[j+1]과 P'[1]가 일치한다면 next[j+1]=1을 넣는다. P[j+k]와 P'[k]가 불일치 하는 지점까지 next[j+k]=k를 넣어준다.
5) 불일치 하는 지점이 있다면 next[]를 채워주고 한 칸 이동한다. 만약 이동했는데 next[]가 채워져 있다면 불일치 지점 까지 next[]가 채워져있는지 확인하고, 채워져있다면 다시 한 칸 이동한다.
6) 하지만 불일치 지점까지 next[]가 채워져 있지 않다면 위의 3)~5) 과정을 반복한다.
이것을 FSM으로 그려보면,
KMP의 FSM이 어떤것을 의미하는지 알려면 next[]와 비교해보면 된다.
FSM에서 화살표가 시작하는 지점과, 화살표가 가리키는 지점이 있는데
화살표가 시작하는 지점을 next[]배열이라고 생각하고, 화살표가 가리키는 지점을 next[]배열이 가진 값이라고 생각하자.
여기서 FSM의 첫번째 문자인 a를 살펴보자.
표에서 P가 가진 첫문자 'a' 의 인덱스인 0 위치에 해당하는 next[0]의 값을 보면 -1이 들어있다.
FMS을 다시 보면,
화살표가 시작하는 지점인 'a'에서,
화살표가 가리키는 지점인 '시작'이라고 적힌 네모칸을 가리킨다.
a 의 next인 next[0]에는 -1이 들어있다는 것을 의미한다.
위와같은 방식으로 P에 해당하는 next[]를 보면 FSM을 쉽게 이해할 수 있다.
이제는 개선된 KMP알고리즘의 FSM에 대해 알아보자.
개선된 KMP알고리즘의 FSM을 만들기 위해서는
위에서 만들었던 KMP알고리즘의 FSM을 이용하는게 가장 빠르다.
개선된 KMP는 P의 next[]가 어떤것을 가리키는지 알아야 한다.
개선된 KMP알고리즘의 코드중, Init() 부분의 for문을 주의해서 봐야한다
int KMP_Search2(char *p, char *a)
{
int i, j, M, N;
M = strlen(p); N = strlen(a);
InitNext2(p); /* next[] 초기화 */
for(i = 0, j = 0; j < M && i < N; i++, j++)
while(j >= 0 && a[i] != p[j])
j = next[j];
if(j == M) return(i-M); /* 일치 문자열 시작 위치 */
else return(N); /* return (-1), 불일치 */
}
InitNext2(char *p)
{
int i, j, M;
M = strlen(p);
next[0] = -1; /* 첫 문자 불일치시 한칸 이동 */
for(i = 0, j = -1; i < M; i++, j++, next[i] = (p[i]==p[j]) ? next[j] : j)
while(j >= 0 && p[i] != p[j])
j = next[j];
}
개선된 KMP알고리즘과 KMP알고리즘의 차이점은, next[i]=(p[i]==p[j])? next[j] : j 부분이라는 점.
KMP알고리즘에서는 next[i]=j를 하는 것으로 next[i]를 채우고 다음으로 넘어갔다.
하지만, 개선된 KMP알고리즘에서는 조건식을 사용해서 한번의 검사를 더 하게 된다.
next[i]=(p[i]==p[j])? next[j] : j
위의 문장을 if-else문으로 바꾼다면
if(p[i]==p[j]){
next[i]=next[j];
}else{
next[i]=j;
}
즉, 화살표 시작점의 원소와 화살표가 가리키는 지점의 원소가 같다면, next[i]에 대입하는 것은 화살표가 가리키는 지점의 원소가 가리키는 지점의 원소가 가진 next[j]를 넣으라는 것이 된다.
위의 FSM에서 화살표의 시작점과 화살표가 가리키는 지점을 보자.
P[0]인 'a'는 -1을 가리키고,
P[1]인 'b'의 next[1]은 P[0]인 'a'를 가리킨다. 화살표 시작점=b, 화살표가 가리키는 지점=a (시작점과 가리키는 점이 다르기 때문에 다음으로 넘어가 P[2]를 확인한다.)
P[2]인 'a'의 next[2]는 P[0]인 'a'를 가리킨다. 화살표 시작점=a, 화살표가 가리키는 지점=a (a와 a가 같다)
P[3]인 'b'의 next[3]은 P[1]인 'b'를 가리킨다. 화살표 시작점=b, 화살표가 가리키는 지점=b (b와 b가 같다)
P[4]인 'b'의 next[4]는 P[2]인 'a'를 가리킨다. 화살표 시작점=b, 화살표가 가리키는 지점=a (시작점과 가리키는 점이 다르기 때문에 다음으로 넘어가 P[5]를 확인한다.)
P[5]인 'a'의 next[5]는 P[0]인 'a'를 가리킨다. 화살표 시작점=a, 화살표가 가리키는 지점=a (a와 a가 같다)
P[6]인 'a'의 next[6]은 P[1]인 'b'를 가리킨다. 화살표 시작점=a, 화살표가 가리키는 지점=b (시작점과 가리키는 점이 다르기 때문에 다음으로 넘어가 P[7]을 확인한다.)
P[7]인 'a'의 next[7]은 P[1]인 'b'를 가리킨다. 화살표 시작점=a, 화살표가 가리키는 지점=b (시작점과 가리키는 점이 다르다는 것을 확인했다.)
이렇게 봤을 때,
이렇게 개선된 KMP도 FSM으로 확인할 수 있다.
'--------------------**** > 알고리즘' 카테고리의 다른 글
| 다단계 합병에서 런의 분포 (0) | 2019.12.27 |
|---|---|
| 깊이 우선 순회 DFS - 스택 이용 (0) | 2019.12.26 |
| AVL 트리 설명 (0) | 2019.12.24 |
| KMP알고리즘 코드로 이해하기 (0) | 2019.12.23 |
| 알고리즘 공부했던 방법 (1) | 2019.12.14 |
