String Matching

728x90

Problem definition (문제 정의)

text : simple string of characters (문자열을 찾을 텍스트)
pattern : simple string of characters (찾을 텍스트 - 패턴)
to do : find where in the text the patter occurs 패턴이 나타나는 텍스트 찾기

Algorithm

Algorithm	시간	공간
naive	\(O(mn)\)	\(O(n)\) or \(O(1)\)
DFA (Deterministic Finite Automaton)	\(O(\sum m + n)\) - 테이블 제작 + 텍스트 읽기	\(O(\sum m\) - 테이블 메모리
KMP (Knuth Morris Pratt)	\(O(m+n)\)	\(O(m)\)

* n : 텍스트의 길이 / m : 패턴의 길이 / \(\sum m\) : 패턴에 나오는 알파벳의 집합

* O(m+n) 보다 빠를 수 없음 (존재하기는 함) : 입력의 글자수가 그만큼을 차지하기 때문임

Naive

글자 전까지 매치시킬 수 있는 최대 패턴의 길이를 확인함 > output에 숫자 형태로 적어줌

ex ) pattern : abcabcd

text	a	b	a	b	c	a	b	c	a
output	1	2	1	2	3	4	5	6	4

Q. 왜 맨 마지막이 4일까?

A. 최대로 매치시킬 수 있는 것은 abca까지 4개 이기 때문

int naivematch(char T[], int n , char P[], int m, int output[]){
	int i, j, k, kk;
	//output은 전부 다 0 초기화
	for (i = 0; i < n ; i++){
		for(j = 0; j< m; j++){
			if (T[i+j] == P[j]) output[i+1] = max(output[i+1], j+1);//이미 적혀잇는게 크면 적지 않음
			else break;
		}
	}
}

텍스트와 패턴을 하나하나 모두 비교해가면서 output의 숫자를 업데이트 해줌
먼저 적은 output이 나중에 적은 output보다 크기 때문에 큰 숫자를 적어주는 과정이 필요함

DFA Algorithm

* 테이블이 주어진다고 가정하자

ex) pattern : abcabcd

int Table [4][8] = {테이블 / 패턴을 읽어서 이 표를 만드는 코드가 존재해야함}

// 테이블 사용
int DFAmatch(char T[], int n, int output[]){
	int i,s;
	s = 0; // 현재 상태
	for (i = 0; i < n; i ++){
		output[i] = s = Table[T[i] - 'a'][s]; // 현재 위치에서 읽은 문자 // 문자를 숫자로 만들어주기 위함
		
	}
}

table에 주어진 상태를 미리 가지고 돌아가고 있음
0번 상태에서부터 차례대로 읽어나가는 방식 (output을 채우는 방식이 table이라고 생각하기)
0번 상태를 초기 상태라고 생각하고 패턴의 첫번째 글자를 읽으면 1번 상태로 가는 과정을 계속해서 반복함
패턴이 7글자라면, 7번까지의 상태가 나타남
테이블의 가로 길이 : m+1
테이블의 세로 길이 : \(\sum m\)

KMP

숫자의 의미 (output의 의미) : 이 자리까지 주어진 패턴의 앞부분과 일치하도록 놓을 수 있는 길이 / 개수

> 다 똑같아질 수 있는 가장 긴 길이

Q. 6다음에 7이 오는 이유는 무엇인가?

A. 7보다 큰 숫자가 온다면, 앞이 6보다 커야한다. 하지만, 앞이 6이기 때문에 7보다 큰 숫자가 올 수가 없다.

ex) 0 1 3 6 9 failure function이 제공

0 1 3 6 9가 놓을 수 있는 모든 경우의 수라는 것을 의미함
dfa 테이블과 같은 의미를 가짐
가장 많이 겹칠 수 있는 경우를 보여준다.

step

1. 9개의 값이 같을 때 (failure function에서 제공됨) : 다음 숫자가 같다면 - 10, 다르다면 6을 비교한다

2. 6개의 값이 같을 때 : 다음 숫자가 같다면 7, 다르다면 3을 비교한다

3. 3개의 값이 같을 때 : 다음 숫자가 같다면 4, 다르다면 1을 비교한다

4. 1개의 값이 같을 때 : 다음 숫자가 같다면 2, 다르다면 0을 비교한다

5. 0개의 값이 같을 때 : 다음 숫자가 같다면 0, 다르다면 다음 텍스트로 넘어가서 다시 비교를 시작한다.

>> 즉 최대 같을 수 있는 숫자들의 경우가 0, 1, 3, 6, 9 이므로 7,4,2,1,0의 숫자들만 output에 가능하다

Failure function 의 정의

pattern p의 앞부분 k글자까지 매치되었을 때 다음번 시도할 pattern 앞 부분의 길이

로직 : p랑 p를 비교하는 kmp와 같다고 볼 수 있음

int f[8] = {-1, 0, 1, 1, 2, 2, 3, 4, 5, 6, 8, 4, 1};//0은 안쓰는 칸

int KMPmatch(char T[], int n, int output[])[
	int i, s;
	for (i = 1; s = 1; i <= n; i++, s++){
			// i text index, s pattern index
			// 패턴의 첫 글자는 스페셜 케이스 > 맞으면 1, 틀리면 0 faliure funciton이 없음
			if(s == 1){ //둘 다 첫번째 글자 보기( 스페셜 케이스 )
				if(T[i] == P[s]) output[i] = s; 
                else s=0; output[i] = 0;//s = 0 이여야만, 루프가 끝나고 1로 업데이트 됨
            }
			else {
				if(T[i] == P[s]); output[i] = s; 
				else s = f[s-1]; i--; //failure function을 이용해서 retry
			} 
	}
}

amortized analysis

루프마다 실행시간이 다름
계산1 : 루프횟수 * 가장 오래 걸리는 경우의 시간
계산2 : 각 루프의 실행시간을 모두 따져서 더함

텍스트에서 다음 글자로 가는 것 : n

패턴을 미는 것 : n

아무리 많아도 2*n의 시간이 걸림 O(n)

failure funtion을 만드는 시간이 O(m)

따라서 O(m+n)의 시간을 소모함