자료구조 4주차

자료구조 4주차

• String matching

: 문자열 일치

: 완전히 같다 수준을 이야기함

: 배열에서 문제를 품

• Problem Definition
  • Text : simple string of characters
  • pattern : simple string of characters
  • to do : whre in the Text the Pattern occurs
• 알고리즘

알고리즘	Naive (BruteForce)	DFA (Deterministic Finite Automation)	KMP (Knuth, Morris, Pratt)
시간	O(mn)	O(	E
공간	O(n)	O(m+n)	O(m)
- 답만 계산하는 것보다 추가적으로 더 계산하는 게 편할 때가 있음

---

char T[100] = { 'a','b','a','b','a','b','c','a','b','c','a','b','c','d','a','b','c','c','b','a','a','b','d','a', 'b', 'c', 'a', 'b', 'c','d','a','b','c','d' };
char P[100] = { 'a','b','c','a','b','c','d' };

기준은 위와 같은 원소를 가진 배열로 한다.

---

Naive 알고리즘

• 매칭시킬 수 있는 패턴의 앞 부분의 가장 긴 문자열의 길이 ← 글자 위에 적힌 숫자의 의미
  • → length(x)가 곧 정답
• 계산하기

#include <bits.stdc++.h>

using namespace std;

int output[100];
void naivematch(char T[], int n, char P[], int m, int output[]) {
        int i, j;
        for (i = 0; i < n; i++) { // Text 0~n-1번째 인덱스까지 비교 시작
                /*j = 0; // j는 패턴의 인덱스
                while (j < m && i + j < n && P[j] == T[i + j]) {
                        j++;
                        output[i + j] = max(output[i + j], j);
                        cout << "i랑 j 출력" << "\n";
                        cout << "i : " << i << " " << "j : " << j << "\n";
                        cout << "output[i + j] == " <<output[i+j]<<endl;
                }*/
                int check = 0;
                for(j=0;j<m;j++){
                        if(i+j>n){ //배열 밖으로 나가면 return
                                return;
                        }
                        if(T[i+j]==P[j]){ // 같으면 j만 ++; check, output[i+j] 중 큰 값을 output[i+j]로
                                check++;
                                output[i+j] = max(check, output[i+j]);
                                continue;
                        }
                        for (int i = 0; i < 34; i++) {
                                cout << output[i] << " ";
                        }
                        cout << "\n";
                        break;
                }
        }
}
int main() {
        char T[100] = { 'a','b','a','b','a','b','c','a','b','c','a','b','c','d','a','b','c','c','b','a','a','b','d','a', 'b', 'c', 'a', 'b', 'c','d','a','b','c','d' };
        char P[100] = { 'a','b','c','a','b','c','d' };
        naivematch(T, 34, P, 7, output);
        return 0;
}

• 신기했다. 교수님이 말씀하신 것처럼 대부분 초반 문자열 일치를 확인하기 위한 알고리즘을 짜는 학생 중 한 명이 나였고…
• N : 피검색 문자열 길이 / M : 찾으려는 문자열 길이
• 시간복잡도 : O(MN), for문 2번
• 공간복잡도 : O(N) (or O(1)), 출력사이즈

---

DFA 알고리즘

유일한… + 유한한… + 자동기계 ⇒ 상태도

• 상태도
  • 다음 글자를 읽었는데 현재 상태에 따라 x를 읽으면 1번을… 다르면 2번을…
  • 이런 느낌
• 패턴을 가지고 만드는 상태도
  • 상태번호 → naive에서의 output[] 값과 같음
  • == 맞춰진 글자 수
• 기존에 패턴에 대한 Table 파일을 가지고 알고리즘을 수행

int Table[4][8] = { 
        {1,1,1,4,1,1,4,1},
        {0,2,0,0,5,0,0,0}, 
        {0,0,3,0,0,6,0,0}, 
        {0,0,0,0,0,0,7,0} 
};

int output[100];

char T[34]= { 'a','b','a','b','a','b','c','a','b','c','a','b','c','d','a','b','c','c','b','a','a','b','d','a', 'b', 'c', 'a', 'b', 'c','d','a','b','c','d' };

void DFAmatch(char T[], int n, int output[]) {
        int i, j=0;
        output[0] = 0;
        for (i = 0; i < n; i++) {
                output[i] = Table[T[i]-'a'][j];
                j = output[i];
        }
}

int main() {
        DFAmatch(T, 34, output);
        for (int i = 0; i < 34; i++) {
                cout << output[i] << " ";
        }
        return 0;
}

• DFA 트랜지션 테이블을 생성한 이후 알고리즘 구현
  • 테이블 == t가 무엇인지에 따라 output[i]에 무엇을 적어야하는 지 다 나와 있음.
• 어떤 패턴을 주면 이러한 테이블을 생성하는 알고리즘이 존재한다. (이는 O(ΣM)의 시간복잡도, 공간복잡도를 가진다.)
• ΣM : M을 사용하는 문자 종류만큼 더한 것(abcabcd를 찾는 경우 7*4), 트랜지션 테이블 공간 크기.
• 시간복잡도 : O(ΣM + N), 트랜지션 테이블 제작시간 + for문
• 공간복잡도 : O(ΣM), 트랜지션 테이블 공간

---

---

KMP 알고리즘

• t와 s가 같은 경우, 다를 경우만 생각하기
• 9 = 요 글자까지 포함해서 string matching 시킬 수 있는 가장 긴 길이
• 글자들이 똑같도록 놓을 수 있는 길이가 여러 개 더 있을 수 있음
• [0,1,3,6,9]
  • 이거는 text와는 상관이 없음
• 9 → t에서 s와 다르면
  • 6,3,1,0도 try 해봐야 한다.
• 9에서 다음 글자를 봤을 때 실패하면 무조건 6으로 가서 봐야함
  • 패턴의 9번째 글자에 6이라고 적혀 있는 상황
  • ex ) 패턴의 6번째 자리에, 스페셜 벨류로 3이 이미 적혀 있음.

자료구조 김성렬 교수님 강의자료

• 6,3,1,0 =⇒ 글자들이 다 똑같게 되도록 놓을 수 있는 길이
• 6인 케이스

자료구조 김성렬 교수님 강의자료

• 9,6,3,1,0 ⇒ text와는 상관 없음
• 9,6,3,1,0 이 있다면 9,4,2,1,0이 나올 수는 없음!

자료구조 김성렬 교수님 강의자료

→ 이 9,6,3,1,0을 어떻게 계산할 건가?

• Failure Function 정의
  • Pattern P의 앞부분 k글자까지 매치되었을 때 다음 번 시도할 Pattern 앞 부분의 길이

int f[6] = { -1,0,1,3,6,9 }; // 1번째 -1은 스페셜 값
int KMPmatch(char T[], int n, int output[]) {
        int i, s; // T의 i번째 서칭중
        i = 0; s = 0; // 첫 글자에 놓고 시작 , s는 여태까지 match된 글자
        while (i <= n) {
                if (P[s + 1] == T[i]) {
                        output[i] = s + 1;
                        i++;
                        s++;
                }
                else {
                        if (s == 0) { // 매치가 안되었을 때 s가 0이라면
                                output[i] = 0; // output에 0을 적고 i++;
                                i++; // text가 움직이는 게 최대 n번
                        }
                        else { // i는 변화시키지 않고 s만 변화시키기
                                     // 다음번 retry할 곳으로 가는 것
                                s = f[s]; // pattern이 움직이는 게 최대 n번
                        }
                }
        }
}
/*
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값만 줄인다.
            // 같은 문자에 대해 재시도를 하게 된다.
        }
    }
}
*/

• 패턴에 s번째 글자까지 매치, i번째 글자를 비교

자료구조 김성렬 교수님 강의자료

• s=f[s] 부분이 구현되는 원리
• Failure Function 계산
  • Pattern P의 앞부분 k글자까지 매치되었을 때 다음 번 시도할 Pattern 앞 부분의 길이
  • 9 → 6으로 가는 걸 어떻게 아냐?
    • 특정 위치에 failure function을 얼마 적을 지 계산하는 거는
    • 그 앞자리 failure function을 보고 x라면
    • 앞에 x글자가 같다는 것

---