[자료구조] String Matching

• 본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다.
• 따라서 완벽하지 않은 부분이 있을 수 있습니다.
• 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다.

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
• 공간복잡도 : O(m), failure func의 공간

분할상환 분석(Amortized Analysis)

• 루프 마다 실행 시간이 다르다.
• 계산1 : (루프 횟수) * (가장 오래 걸리는 경우의 시간)
• 계산2 : 각 루프의 실행 시간을 모두 따져서 더한다 -> 분활상환 분석의 방법