kmp 알고리즘에서 preprocessing(전처리) 과정에 관한 질문입니다.
글쓴이: canuyes / 작성시간: 목, 2013/03/28 - 12:47오후
안녕하세요?
현재 kmp알고리즘을 공부중에 있는 학생입니다.
kmp알고리즘을 공부중 전처리과정(preprocessing)의 구현에 관한 어려움믈 겪고 있어 질문남깁니다.
제가 공부중인 서적과 다수의 웹자료에 전처리과정은 아래와 같이 구현되어있습니다.
void preprocess(char* pattern,int* table){
int len=strlen(pattern);
int i=0,j=-1;
table[0]=-1;
while(i<len){
while(j>-1&&pattern[i]!=pattern[j]){
j=table[j];
}
i++;j++;
table[i]=j;
}
return;
}3시간 가량 생각해보고 고민해보았는데 코드가 이해가 되질않네요..
자괴감만 커져 갑니다...ㅠㅠ
strcmp등을 이용하여 직접 접두부를 찾는 방법도 생각해보았지만
그런 방법을 선택시에 위의 코드보다 복잡도가 크게 증가한다고 하네요...
구글링중 다음 링크하단에서 꽤나 충실한 설명을 보았지만
http://211.228.163.31/30stair/KMP_DOC1/KMP_DOC1.php?pname=KMP_DOC1
부족한 능력 탓인지 이해가 잘 되지 않네요...
혹시 kmp 알고리즘의 전처리과정의 알고리즘에 대해 알려주실수 있으신가요?ㅜㅜ
이제 곧 점심시간이라 점심전에 올려봅니다 ㅠㅠ
Forums:
제가 이해한걸 쓴
제가 이해한걸 쓴 글입니다.
http://dol9.tistory.com/122
전처리 과정이라는게,
어느 위치에서 틀렸을때 어디로 이동할거냐를 정하는 건데,
뭉탱뭉탱 움직이기위해 prefix, suffix를 사용한다고 생각했습니다.
도움이 됐으면 좋겠네요
답변 감사합니다.
답변 감사드립니다.
그런데 전 kmp의 진행과정보다는 kmp의 preprocessing의 작동원리가 궁금합니다. ㅜㅜ
링크에는 preprocessing 자체에 초점이 맞추어져 있지는 않는것 같네요...
계속 구글링 하던중
http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm
에서 나름 만족할만한 설명을 찾았습니다.
하지만 아직 구현된 코드가 맞는 건 알겠으나, 머리속에서 정리되서 스스로 작성할 수 있을 정도로 이해한것은 아닌것같습니다.
추후에 혹시 preprocessing 함수에 대해 더 설명해주 실 수 있으시다면 설명해주세요..
답변 정말 감사드립니다. ㅠㅠ
도움이 되었으면 좋겠습니다
안녕하세요,
1년 전 글이지만 답글을 달아봅니다
fail table의 아이디어는
"pattern vs source text"를 비교함으로써 알게 되는 것을 "source text"가 없는 상황에서도
"pattern vs pattern"을 통해 미리 예측하는 것으로 생각하고 있습니다
소스에서 보면 아무래도 j = table[j] 부분이 제일 난해한 것 같은데요
예제 없이 이해하기가 쉽지 않은 것 같습니다
1. 먼저 아래와 같은 패턴을 선정하고 미리 fail table을 계산한 결과입니다
① 패턴 BABBACAA
② fail table
0 1 2 3 4 5 6 7 8 : Array index
B A B B A C A A : Pattern
-1 0 0 1 1 2 ? : border
########################################################################################
border == 경계 란?
해당 문자 바로 전까지의 pattern 에서 prefix & postfix가 최대로 겹치는 넓이로써
pattern이 dismatch 되었을 때, 새로 정해지는 pattern의 index 입니다
비교대상 text의 index가 1씩 증가함에 있어서 border가 클 수록 pattern의 시작 index가 커지며
이로 인해 다음 비교 시, 0~index-1 까지를 skip 하게 됩니다
########################################################################################
2. "A"에 대한 경계값 구하기를 예로 든다면, 아래와 같은 상황일 것입니다
(1) matching fail 발생
B A B B A C | A
B A B B A C | X
(2) A에서 매칭 되지 않았다면 BABBAC 까지는 매칭 되었음을 뜻하며 이는 소스에서 A의 경계값을 구하는 동안에 i==5인 이유가 됩니다
A의 경계값으로 BABBAC의 접두사 및 접미사의 일치부분만 찾으면 됩니다
이 때, 이미 구해진 C의 경계값을 이용하는데 경계값은 순차적으로 계산되기 때문에 C의 경계값도 이미 정해진 상태이며 "2"입니다
C의 경계값을 이용하는 이유는 경계값을 최대의 길이로 선정해야 하기 때문입니다
즉, A의 경계값으로 C의 경계값에 1을 더한 길이 3인 값을 찾는 것인데 그 이유는 맨 아래에 예로 들었습니다
(3) 그런데 길이가 3인 경계값을 구하다보면 BAB vs BAC 가 다름을 확인하게 됩니다
아래의 소스가 그 역할을 수행하며 이는 곧 A의 경계값의 크기가 3이 될 수 없음을 의미합니다
while ( j > -1 && pattern[i] != pattern[j] )
j = table[j]
(4) 소스코드를 보면 일치한다고 생각했던 BA"B" vs BA"C" 마저 틀려버렸고 이는 A의 경계값의 크기가 3이 될 수 없음을 뜻합니다
즉, BA"B"가 dismatch 되었을 때를 가정하고 다시 경계값을 계산해야 합니다
j = table[j] 코드를 통해 j는 2가 되고 3번째 "B"의 경계값을 이용합니다
(사실, 경계값이란 main함수에서 pattern의 index를 reset하는 역할이기 때문에
A가 dismatch일 때, BAB"B"의 4번째 문자에서 패턴매칭을 다시 시작하지 못함을 의미합니다 )
#step 1 : A에서 dismatch 발생 (i == 5, j == 2)
B A B B A C | A
B A B B A C | X
#step 2 : pattern[5] != pattern[2] --> j = table[2] (==0)
........ B A | B
B A B B A | C
#step 3 : pattern[5] != pattern[0] --> j = table[0] (==-1)
.............. | B
B A B B A | C
#step 4 : j++, i++
#step 5 : j=-1 , table[6] = -1
(6) 미리 구해진 fail table에 의해서 j=0 이 되고 while문을 통해 pattern[5] != pattern[0] 가 성립합니다
이제 j=-1 이 되며 j++를 통해 table[i]= 0 이 저장되게 됩니다
이로써 A의 경계값은 0이 되며 이는 A에서 disamtch 되었을 때, 패턴의 처음부터 다시 검사해야 함을 뜻합니다
###########################################
경계값이 최대여야 하는 이유
A B A B A B C B : pattern
A B A B A B A B C B : text
# 경계값이 최대일 경우
..... A B A B A B C B : pattern
A B A B A B A B C B : text
# 경계값의 최대가 아닐 경우, text의 두 번째 A부터 시작하는 pattern을 놓치게 됨
........... A B A B A B C B : pattern
A B A B A B A B C B : text
###########################################
오늘도 조금 더 배우는 하루
asd
asd
KMP 전처리 작업이 pattern mismatch
KMP 전처리 작업이 pattern mismatch 시 인덱스를 얼마만큼 조정할 것인가 라는 것만 이해하면
나머지는 스스로 생각해 보셔도 똑같은 알고리즘 나올 듯해요.
알고리즘은 스스로 생각해 보는 게 실력 향상법임.
댓글 달기