자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다.
0. String Matching
긴 텍스트형식의 문자열에서 패턴을 찾아주는 것을 말합니다.
생각보다 실생활에 많이 쓰입니다.
- 워드에서 ctrl+F 를 통해 원하는 단어를 찾는 것
- 웹 페이지에서 원하는 검색어를 갖는 페이지를 찾아주는 것
- 생명공학에서 DNA 염기 서열 중 원하는 염기 서열을 찾아주는 것
- etc...
String Matching 에 사용되는 용어들과 문제를 재정의 해보겠습니다.
Text : Simple String of Characters
Pattern : Simple String of Characters to find
To Do : Find where in the Text the Pattern is
0.1 알고리즘
| 알고리즘 | 시간 | 공간 |
| Naive | O(mn) | O(n) or O(1) |
| DFA(Deterministic Finite Automaton) | O(|∑|m + n) | O(|∑|m) |
| KMP(Knuth, Morris, Pratt) | O(m+n) | O(m) |
- n : length of Text
- m : length of Pattern
- ∑ : set of characters we used in pattern(called Alphabet)
이렇게 3가지의 알고리즘들이 존재합니다.
우리가 하고싶은 것은 Text 안에 Pattern 이 있다면 어디에 존재하는지를 알려주는 것 입니다. 이를 위해 Pattern 이 존재한다는 것이 무엇인지, 다시 정의할 필요가 있습니다.
계산하고자 하는 값은
Text 안에 있는 각 Character 들에 대해
그 글자를 포함하여 그 앞으로 존재할 수 있는
Pattern 의 최대 길이
해봅시다.
말은 어렵지만 예시를 들면 간단합니다.
Text : ababcabda
Pattern : abc
라고 해봅시다.
그러면
| Text: | a | b | a | b | c | a | b | d | a |
| Pattern | a | b | c | ||||||
| output | 1 |
우선 이렇게 됩니다. Text 의 가장 첫 번째 a 는 그 앞으로 Pattern 이 1개 밖에 나오지 못합니다. 그래서 output 은 1 입니다.
| Text: | a | b | a | b | c | a | b | d | a |
| Pattern | a | b | c | ||||||
| output | 1 | 2 |
Text 의 두 번째 글자인 b 는 b 앞으로 Pattern 이 최대 2 글자 나올 수 있으니 output 은 2 입니다.
| Text: | a | b | a | b | c | a | b | d | a |
| Pattern | a | b | c | ||||||
| output | 1 | 2 | 1 |
Text 의 세 번째 글자인 a는 a 앞으로 Pattern 이 최대 1 글자 나올 수 있으니 output 은 1 입니다. 이렇게 쭉쭉 이어나가면...
| Text: | a | b | a | b | c | a | b | d | a |
| Pattern | a | b | c | ||||||
| output | 1 | 2 | 1 | 2 |
| Text: | a | b | a | b | c | a | b | d | a |
| Pattern | a | b | c | ||||||
| output | 1 | 2 | 1 | 2 | 3 |
| Text: | a | b | a | b | c | a | b | d | a |
| Pattern | a | b | c | ||||||
| output | 1 | 2 | 1 | 2 | 3 | 1 |
| Text: | a | b | a | b | c | a | b | d | a |
| Pattern | a | b | c | ||||||
| output | 1 | 2 | 1 | 2 | 3 | 1 | 2 |
| Text: | a | b | a | b | c | a | b | d | a |
| Pattern | a | b | |||||||
| output | 1 | 2 | 1 | 2 | 3 | 1 | 2 | 0 |
| Text: | a | b | a | b | c | a | b | d | a |
| Pattern | a | ||||||||
| output | 1 | 2 | 1 | 2 | 3 | 1 | 2 | 0 | 1 |
따라서 결과 배열중 Pattern 의 길이에 해당하는 값이 있는 곳이 Pattern 이 존재하는 곳이라고 알 수 있습니다.
그렇다면 문제 정의는 끝났습니다.
Text 안에 있는 각 Character 들에 대해
그 글자를 포함하여 그 앞으로 존재할 수 있는
Pattern 의 최대 길이
를 나타내는 output 배열을 만들어라!!
1. Naive 알고리즘
순진해 빠지게 찾아보는 방법입니다.
패턴을 각 텍스트 하나하나와 비교해가며 output 을 얻어냅니다.
코드를 보고 설명하겠습니다.
char string[] = "abababcabcabcdabccbaabdabcabcdabcd";
char pattern[] = "abcabcd";
int* output = new int[sizeof(string)/sizeof(string[0]) - 1];
int patternLength = sizeof(pattern) / sizeof(pattern[0]) - 1;
int stringLength = sizeof(string) / sizeof(string[0]) - 1;
int naive(){
/*
@param i is index to use in the text
@param s is index to use in the pattern
*/
int i, s;
// output 0 으로 초기화
for(int j=0; j<stringLength; j++){
output[j] = 0;
}
for(i = 0; i < stringLength - patternLength; i++){
for(s = 0; s < patternLength; s++){
if(string[i+s] == pattern[s])
{
output[i] = output[i] < (s+1) ? (s+1) : output[i];
}
else
{
break;
}
}
}
}
}
int main(){
naive();
for(int i=0; i<stringLength; i++)
{
std::cout << output[i] << " ";
}
return 0;
}
처음은 다음과 같이 시작합니다.
| Text: | a | b | a | b | c | a | b | d | a |
| Pattern | a | b | c | ||||||
| output | 1 |
i=0, s=0 인 상태에서 string[0+0] 과 pattern[0] 이 같으므로 output[0] 에 0+1 을 넣어주고 s++ 해줍니다.
| Text: | a | b | a | b | c | a | b | d | a |
| Pattern | a | b | c | ||||||
| output | 1 | 2 |
i=0, s=1 인 상태에서 string[0+1] 과 pattern[1] 이 같으므로 output[1] 에 1+1 을 넣어주고 s++ 해줍니다.
| Text: | a | b | a | b | c | a | b | d | a |
| Pattern | a | b | c | ||||||
| output | 1 | 2 |
i=0, s=2 인 상태에서 string[0+2] 와 pattern[2] 가 다르므로 for 문을 탈출하고 i++ 해줍니다.
| Text: | a | b | a | b | c | a | b | d | a |
| Pattern | a | b | c | ||||||
| output | 1 | 2 |
i=1, s=0 인 상태에서 string[1+0] 과 pattern[0] 과 다르므로 for 문을 탈출하고 i++ 해줍니다.
| Text: | a | b | a | b | c | a | b | d | a |
| Pattern | a | b | c | ||||||
| output | 1 | 2 | 1 |
i=2, s=0 인 상태에서 string[2+0] 과 pattern[0] 이 같으므로 output[2] 에 0+1 을 넣어주고 s++ 해줍니다.
이런식으로 계속 수행해 나가면 output 배열을 채울 수 있습니다.
여기서 왜 string 과 pattern 이 같을 때 삼항연산자를 사용했는지 궁금하다면 더보기를 눌러주세요.
만약 pattern 이 abab 이고, string 이 abacababd 라고 한다면
| Text: | a | b | a | c | a | b | a | b | d |
| Pattern | a | b | a | b | |||||
| output | 1 | 2 | 3 |
까지는 i++ 를 하지 않고 진행하고 string[3] 과 pattern[3] 이 다르므로 for 문을 탈출, i++ 를 합니다.
| Text: | a | b | a | c | a | b | a | b | d |
| Pattern | a | b | a | b | |||||
| output | 1 | 2 | 3 |
string[1] 과 pattern[0] 이 다르므로 for 문을 탈출하고 i++ 를 합니다.
문제는 여기인데
만약 삼항연산자를 통해 기존에 있던 값과 새롭게 추가할 값의 최대값을 넣어주지 않는다면 이렇게 됩니다.
string[2] 와 pattern[0] 이 같으므로 s+1 을 저장하면 output[2] 에는 1이 들어가게 됩니다. 하지만 정상적이라면 output[2] 에는 기존의 값인 3이 들어가야 합니다.
| Text: | a | b | a | c | a | b | a | b | d |
| Pattern | a | b | a | b | |||||
| output | 1 | 2 | 1(추가) |
이런 경우를 방지하기 위해서 삼항연산자를 사용합니다.
1.1 시간복잡도
for 문이 두 번 중첩되기 때문에 O(NM) 입니다.
1.2 공간복잡도
String 이 저장되는 배열의 크기 N, Pattern 이 저장되는 배열의 크기 M 만이 필요하기 때문에 공간복잡도는 O(N+M) 입니다.
2. DFA (Determinisic Finite Automata, 결정론적 유한 상태 기계)
결정론적 유한 상태 기계를 만들어 문자열에서 패턴을 추출합니다.
- 계산이론의 한 분야인 이론 전산학에서 결정론적 유한 상태 기계(Deterministic finite automaton, DFA)는 각각의 입력 문자열 안의 각 심볼에 대하여 유일한 상태변화를 취하는 유한 상태 기계이다.[1] 이 용어에서 결정적이란 계산의 유일함을 뜻한다. (- WIKIPEDIA)
여기에서 상태를 앞서 정의한 output 으로 정의한다면, 문자열을 읽어가면서 output 을 적어나갈 수 있습니다.
유한 상태 기계가 만들어져 있다면 별로 문제가 어렵지 않습니다. 하지만 유한 상태 기계를 어떻게 만들지가 중요한 문제입니다. 여기에서는 이는 생략하고 시간 복잡도 O( |∑|m) 에 해당 기계를 만들 수 있다고 하겠습니다.
해당 기계는 행렬로 나타낼 수 있습니다.
만약 pattern 이 abcabcd 라고 한다면 유한 상태 기계(* table[][])는 다음과 같습니다.
| status | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| a | 1 | 1 | 1 | 4 | 1 | 1 | 4 | 1 | |
| b | 0 | 2 | 0 | 0 | 5 | 0 | 0 | 0 | |
| c | 0 | 0 | 3 | 0 | 0 | 6 | 0 | 0 | |
| d | 0 | 0 | 0 | 0 | 0 | 0 | 7 | 0 |
status 가 0 인 것은 output 이 0 인 것과 같은 의미로
해당 글자를 포함하여 그 글자 앞에 존재할 수 있는 pattern 의 길이가 0 인 것입니다.
그런 상태에서 a 를 입력받으면 status 는 1로 바뀝니다.
즉 table[0][a] 는 status 가 0 일 때, a 를 입력받으면 변하는 status 로 해석할 수 있습니다.
status 가 1 인 상태에서 a 를 입력받으면 output 은 1이 되고, b 를 입력받으면 status 는 2로 바뀌고 output 은 2가 됩니다.
이런 테이블이 이미 존재한다고 했을 때, StringMatching 함수는 다음과 같습니다.
char string[] = "abababcabcabcdabccbaabdabcabcdabcd";
char pattern[] = "abcabcd";
int* output = new int[sizeof(string)/sizeof(string[0]) - 1];
int patternLength = sizeof(pattern) / sizeof(pattern[0]) - 1;
int stringLength = sizeof(string) / sizeof(string[0]) - 1;
int DFA()
{
int dfaTable[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 status = 0;
for(int i=0; i<stringLength; i++)
{
status = dfaTable[string[i] - 'a'][status];
output[i] = status;
}
}
int main(){
DFA();
for(int i=0; i<stringLength; i++)
{
std::cout << output[i] << " ";
}
return 0;
}
2.1 시간복잡도
DFATable 을 만드는 데 걸리는 시간복잡도가 O(|∑|m) 이고 String 의 길이만큼 for 문을 반복하니까
전체의 시간복잡도는 O( |∑|m + n) 입니다.
2.2 공간복잡도
DFATable 을 위한 공간 O(|∑|m) 이 필요하니, 공간복잡도는 이와 같습니다.
2.3 단점
해당 패턴에서 사용하는 알파벳 집합의 원소의 개수가 많으면 수행하는데 걸리는 시간이 매우 길어집니다. 이를 개선하기 위해 KMP 가 나왔습니다.
3. KMP (Knuth, Morris, Pratt)
KMP 는 Naive 방식에서 추가로 성능을 개선한 방식입니다. KMP 에서는 실패함수(* failure function) 을 사용합니다.
실패함수는 해당 글자에서 틀렸을 때 다음 도전할 글자를 알려주는 함수입니다.
실패함수는 배열로 구현됩니다.
실패함수의 index 에 대해
해당 글자 앞에 index 글자가 일치하고 해당 글자가 틀렸을 때
다음 도전할 pattern 의 index 를 실패함수[index] 가 알려줍니다.
Naive 방식에서는 패턴과 문자열이 다른 경우 패턴의 처음부터 다시 비교를 했는데
실패함수가 있다면 무조건 처음부터가 아닌 다음 비교할 수 있는 최선의 자리부터 다시 비교합니다.
이는 확실한 성능 개선을 보여줍니다.
그렇다면 실패함수는 어떻게 만들까?
일단 실패함수의 index=0 의 값은 무조건 0 입니다.
해당 글자 앞에 글자들도 패턴과 하나도 맞지 않고 해당 글자도 맞지 않은 경우에는 다시 도전할 패턴의 index 는 0 입니다.
실패함수의 index=1 의 값은 패턴과 패턴끼리 StringMatching 을 했을 때의 output 의 값과 같습니다.
만약 해당 위치에서의 output 이 0 이면, 즉 해당 글자 앞에 존재할 수 있는 패턴의 최대 길이가 0 이면 다시 패턴의 처음부터 비교해야 하니 실패함수의 값 또한 0 입니다.
만약 해당 위치에서의 output 이 1 이면, 패턴의 인덱스 1 번 부터 비교하면 됩니다.
실패함수의 index=2 의 값도 마찬가지입니다.
말로 설명하기 너무 어려우니 바로 코드를 보며 설명하겠습니다.
char string[] = "abababcabcabcdabccbaabdabcabcdabcd";
char pattern[] = "abcabcd";
int* output = new int[sizeof(string)/sizeof(string[0]) - 1];
int patternLength = sizeof(pattern) / sizeof(pattern[0]) - 1;
int stringLength = sizeof(string) / sizeof(string[0]) - 1;
int KMP()
{
int* failure = new int[patternLength + 1];
failure[0] = 0;
int s = 0;
for(int i=1; i<patternLength+1; i++)
{
if(pattern[i] == pattern[s])
{
failure[i] = s+1;
s++;
}
else
{
if(s == 0)
failure[i] = s;
else
{
s = failure[s-1];
i--;
}
}
}
int k = 0;
for(int i=0; i<stringLength; i++)
{
if(string[i] == pattern[k])
{
output[i] = k+1;
k++;
}
else
{
if(k == 0)
output[i] = 0;
else
{
k = failure[k-1];
i--;
}
}
}
delete[] failure;
}
int main(){
KMP();
for(int i=0; i<stringLength; i++)
{
std::cout << output[i] << " ";
}
return 0;
}
틀렸을 경우 k = failure[k-1] 을 수행하는데, k-1 을 통해 index error 가 발생할 수 있는 k=0 의 case 를 예외처리 해주었습니다.
3.1 시간복잡도
failure function 을 만드는데 O(M), 메인 for 문을 도는데 O(N) 이므로 전체는 O(M+N) 입니다.
https://www.quora.com/Why-is-the-time-complexity-of-the-Knuth-Morris-Pratt-algorithm-O-n
Why is the time complexity of the Knuth-Morris-Pratt algorithm O(n)?
Answer (1 of 6): Worst time complexity of KMP algorithm is O(m+n). O(m) time is taken for lps table creation. Once this prefix suffix table is created, actual search complexity is O(n). The thing people get confused of is that there are two indexes. Index
www.quora.com
https://www.w3spot.com/2020/07/kmp-algorithm-explained-in-plain-english.html
KMP Algorithm Explained In Plain English – W3 Spot
Here I am just trying to explain KMP algorithm in plain english. I will also explain worst time complexity & why it is O(m + n). We will take two examples, one with no repeatable character in the pattern & another with repeatable characters in the pattern.
www.w3spot.com
3.2 공간복잡도
failure function 의 길이 만큼의 공간이 추가로 필요하니 O(M) 입니다.
3.3 의의
KMP 알고리즘의 시간복잡도는 O(M+N) 인데 이는 패턴과 텍스트를 읽어들이는 시간과 같으므로 이론상 이보다 빠른 알고리즘을 찾기는 매우 어렵습니다.
'[학교 수업] > [학교 수업] Data Structure' 카테고리의 다른 글
| 자료구조 및 알고리즘 6 - Equivalance Relation about Graph (0) | 2024.04.14 |
|---|---|
| 자료구조 및 알고리즘 5 - Queue and Stack (0) | 2024.04.11 |
| 자료구조 및 알고리즘 3 - Arrays for Search, Insert, Delete (0) | 2024.04.04 |
| 자료구조 및 알고리즘 2 - contd. (0) | 2024.04.04 |
| 자료구조 및 알고리즘 1 - Arrays, Algorithms, Complexity and Recursion (0) | 2024.04.03 |
