아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다.
String Matching
특정 문자열에서 특정 문자열을 찾는 것
ex) abababcabcabcdabccbaabdabcabcdabcd 에서 abcabcd를 찾는 방법
응용 : 워드 / 염기서열 분석
Naive, DFA, KMP 방법
Navie 알고리즘
int naivematch(char T[], int n, char P[], int m, int output[]) {
int i, j, k;
for (i=1; i<=n; i++) output[i] = 0; // output 초기화
for (i=1; i<n-m+1; i++) {
for (j=i, k=1; k<=m; j++, k++) // j를 피검색 대상 문자열의 인덱스, k를 검색 대상 문자열의 인덱스로 활용한다.
if (T[j] != P[k]) break;
if (k == m+1) output[j-1] = 1;
// for문을 다 돌았을 때 k가 m+1이 된 것은 다 매칭되었다는 것. j-1이 매칭된 마지막 문자이므로 1로 매칭여부 표시
}
}
한 칸 씩 이동하면서 비교를 반복하는 가장 단순한 알고리즘
일치하는 경우 해당 경우의 끝나는 값에 1을 표기한다.
1의 갯수가 정답의 갯수가 될 것이다.
N : 피검색 문자열 길이 / M : 찾으려는 문자열 길이
시간복잡도 : O(MN), for문 2번
공간복잡도 : O(N) (or O(1)), 출력사이즈
DFA 알고리즘
Naive 알고리즘에서 각 숫자에 대한 표기를 좀 더 하는 방식이다.
첫 글자와 일치하는 곳이 발견되면 그곳에 1을 표기하고, 그 이후로도 일치할 경우 1씩 더 증가시키면서 표기한다.
만약 표기하려는 수가 이미 표기된 수보다 작다면 표기할 수 없다.
abcabcd에서 abcd를 찾는다면 abcabcd에는 1231234가 표기될 것이다.
찾으려는 글자의 길이 값이 표기된 갯수가 정답의 갯수가 될 것이다.
이에 대한 경우의 수를 표로 만들어 저장하고, 이를 활용한다.
다음은 abcabcd를 찾을 때 경우의 수 표이다. 위 숫자의 표기까지 진행됐을 때, 다음 문자가 a,b,c,d 중 무엇이냐에 따라 다음 표기가 달라짐을 나타낸다.
해당 테이블을 DFA 트랜지션 테이블이라고 한다.
어떤 패턴을 주면 이러한 테이블을 생성하는 알고리즘이 존재한다. (이는 O(ΣM)의 시간복잡도, 공간복잡도를 가진다.)
ΣM : M을 사용하는 문자 종류만큼 더한 것(abcabcd를 찾는 경우 7*4), 트랜지션 테이블 공간 크기.
int Table[4][8] = { {1,1,1,4,1,1,4,1} ...} // abcabcd 문자열을 찾을 때 트랜지션 테이블
int DFAmatch(char T[], int n, int output[]) {
int i, s;
i = 0; s = 0;
output[i] = s; // 0번째 글자는 0이라는 것을 의미, 테이블을 활용하기 위해선 해당 값이 필요하므로 우선 이렇게 시작
for (i=1; i<=n; i++) { // 첫번째 글자부터 확인
output[i] = Table[T[i] - 'a'][s]; // 피대상 문자열의 i번째 값에서 'a'를 뺀다. 그러면 0~3 사이의 값이 나온다. 이를 활용한다.
// s는 직전 문자를 나타내므로 테이블에서 적절한 값을 가져올 수 있게된다. 이를 output에 넣어준다.
s = output[i]; // 다음에 돌때의 s값을 활용하기 위해 넣어준다.
}
}
시간복잡도 : O(ΣM + N), 트랜지션 테이블 제작시간 + for문
공간복잡도 : O(ΣM), 트랜지션 테이블 공간
KMP 알고리즘
핵심원리는 DFA와 유사하지만 여기서 패턴이 비슷한 점을 활용한다. 특정 글자수만큼 매칭이 된 다음 매칭이 실패하면, 그보다 글자수가 적은 앞부분을 가지고와서 비교한다.
Failure Function : KMP 알고리즘에서는 k번째까지 매칭되었을 때 다음 번째에서 실패했을 때에 대비하여 다음 번 시도할 패턴 앞부분의 길이를 미리 설정해놓는다. 예를 들면 9번째까지 매칭된 상태에서 10번째 매칭이 실패했다면, 6번째까지를 가져와서 7번째 매칭을 시도하는 식이다. 이는 유사한 부분을 미리 파악하고 미리 정해놓는다.
abcabcd가 있으면, 6번째 글자 c까지 매칭 성공 후 7번째에서 실패하면 3번째 글자부분을 가져와서 4번째 매칭을 시도하는 식이다.
이와 같은 방식을 사용하면 다시 처음부터 숫자를 대입해 비교하고 넣는 것보다 처리가 빨라질 수 있게 된다.
int f[8] = {-1,0,1,1,2,2,3,4,5,6,8,4,1};
int KMPmatch(char T[], int n, char P[], int m, int output[]) {
int i, s; // i는 피탐색 문자열의 인덱스, s는 DFA에서 처럼 표기한 글자(=매칭된 수)
i = 0; s = 0;
output[i] = s;
while (i <= n) {
if (s == 0) { // 표기된 것이 아무것도 없으면 (첫 시작이면)
if (T[i] != P[s+1]) { output[i] = 0; i++; s = 0;} // 현재문자와 검색대상 문자열의 첫번째 문자가 다르다면? 완전실패
// 0을 표기한 뒤, 문자열의 다음 문자를 찾고 s는 여전히 0이다.
else {output[i] = 1; i++;; s = 1} // 현재문자와 검색대상 문자열의 첫번째 문자가 같다면? 완전성공
// 1을 표기한 뒤, 문자열의 다음 문자를 찾고 s는 이제 1이다.
}
else { // 표기된 것이 있으면
if (T[i] == P[s+1]) {output[i] = s+1; i++; s++;} // 현재문자와 검색대상 문자열의 다음 문자가 같다면? 완전성공
// 1을 표기한 뒤, 문자열의 다음 문자를 찾고 s를 늘린다.
else {s = f[s];} // 현재문자와 검색대상 문자열의 다음 문자가 같다면? 중간실패
// 현재 문자열에 대해서는 아무 작업도 하지않고, Failure Function을 통해 s값만 줄인다.
// 같은 문자에 대해 재시도를 하게 된다.
}
}
}
매칭이 된 이후에 인덱스값을 초기화하는 코드는 빠져있다.
f의 길이를 m이라고 하면, 한 루프당 최대 m번 반복할 수는 있다. 다만 이런 경우는 '중간실패' 케이스가 계속 나오고 failure function이 특이한 형태이어야 한다.
'완전성공' 갯수 + '완전실패' 갯수는 n이다. 중간실패는 반복가능하지만, 완전성공 혹은 완전실패가 되어야 다음 글자를 탐색할 수 있기 때문이다.
'중간실패' 갯수는 최대 n이다. 중간실패를 할 경우 탐색대상 패턴을 '이동시킨다.' 그 말은 즉, 중간실패를 할 수록 패턴이 옮겨서 아무리 단순한 경우라도 피검색대상의 길이인 n보다 많이 이동될 수는 없다.
시간복잡도 : O(m + n), failure func를 만드는 시간 m, 완전성공 및 완전실패, 중간실패의 합 2n 정리하면 m + n
