문자열 알고리즘

1 개요

말 그대로 문자열과 관련된 알고리즘이다. 가장 대표적인 것이 문자열 검색(string search) 알고리즘이며, 사실상 문자열이 문자의 배열이기 때문에 대부분 같은 원리를 통해서 수열에도 적용 가능하다.

2 문자열 검색 알고리즘

어떤 문자열 S에서, 어떤 패턴 P를 찾아내는 알고리즘이다. 문자열 집합에서 어느 한 개의 문자열을 탐색하는 알고리즘은 Trie나 이진 탐색을 참고하길 바란다.

2.1 Native String Search

이름 그대로다. 1번째부터 m번째 글자까지, 2번째부터 m+1번째 글자까지, 이런 식으로 문자열을 일일이 찾아가면서 탐색한다. 이 경우 길이가 각각 n, m인 문자열과 패턴에 대하여 [math]\Theta ((n-m)m)[/math]의 탐색 횟수를 거친다. 작동 시간이 오래 걸리지만, 구현이 편하기 때문에 충분히 작은 입력이라면 이런 알고리즘을 사용하는 것도 나쁘지 않다. ~~회사의 상사 혹은 학교의 교수에게는 나쁘다.~~

2.1.1 코드

#include 
#include 
#define TRUE 1
#define FALSE 0
typedef int BOOL;
void find_pattern(const char* pszString, const char* pszPattern)
{
int nStrLength, nPatternLength;
int i, j;
BOOL bFlag = TRUE;
nStrLength = strlen(pszString);
nPatternLength = strlen(pszPattern);

for(i = 0; i

2.2 Finite-state automaton based search

그냥 오토마타라고 부르기도 하며, 선형 시간의 효율성을 자랑하는 알고리즘이지만, 후술할 KMP 알고리즘이 해당 알고리즘보다 빠르고 더 이해하기도 쉽다. 이 알고리즘은 상태전이함수를 만들어야 하는데, 그 탐색 횟수까지 고려해야 한다. 따라서 전체 탐색 횟수는 [math]\Theta(n + m| \Sigma |)[/math]. 이때 [math]| \Sigma |[/math]는 문자열에 속해 있는 문자의 종류의 개수이다. 상태를 나타내는 p, 현재 문자열의 위치에 있는 문자의 종류를 나타내는 q가 있다면, 상태전이 함수 [math]p = \delta[p][q][/math] 를 n번 반복해주다가 최종 상태에 돌입하면 매칭된 위치를 출력해주면 된다. 자세한 사항은 오토마타를 참조.

2.2.1 코드

추가 바람

2.3 Knuth-Morris-Pratt Algorithm

발견자들의 앞글자를 따서 KMP라고 읽기도 한다. 앞에서 설명한 오토마타와 비슷한 형식을 따르나 상태전이함수가 훨씬 간결하고, 준비 과정도 선형 시간인 점을 생각하면, 문자의 종류가 다양한 상황^[1]에서라면 당연히 KMP를 선택해야 메모리와 시간 양측에서 이득을 볼 수 있다. ~~근데 대부분의 많은 언어들에는 문자열 탐색 기능이 있어서 잊힌 존재이다...~~ ~~아냐 C 프로그래머라면 안 잊었을지도!~~ ~~자고있던 strstr: ??~~^[2] KMP의 사용 방법은 다음과 같다.

"abcdabckl"이라는 문자열이 있다고 하자. 이때 i = -1, j = 0이며, 시작 위치의 상태함수에 들어갈 값은 -1이다.
i와 j를 한 칸씩 전진시킨 뒤 비교한다.
i와 j가 매치되면 혹은 i == -1일 때 한칸씩 전진한 뒤, j 위치에 i를 저장한다.
만약 i와 j가 매치되지 않는다면 i는 상태전이함수에 있는 값으로 전환시킨 뒤 2로 돌아간다.
j가 n보다 커질 때까지 반복한다.
이 과정을 거친 상태전이함수는 0 0 0 0 1 2 3 0 0이 된다.

이 때의 계산횟수는 [math]\Theta (n+m)[/math]이다.

2.3.1 코드

//상태전이함수 생성
void kmp(char *pat) {
int n = strlen(pat);
int i = -1, j = 0;
pi[j] = i;
while(j n) {
span style="color: #008800; font-weight: bold"if/span(i span style="color: #333333"==/span span style="color: #333333"-/spanspan style="color: #0000DD; font-weight: bold"1/span span style="color: #333333"||/span (i span style="color: #333333">= 0 && pat[i] == pat[j])) {
i++;
j++;
pi[j] = i;
}
else i = pi[i];
}
}
//문자열 비교
void find_pattern(char *arr, char *pat) {
int n = strlen(arr);
int m = strlen(pat);
int i = 0, j = 0;
while(i n) {
span style="color: #008800; font-weight: bold"if/span(j span style="color: #333333"==/span span style="color: #333333"-/spanspan style="color: #0000DD; font-weight: bold"1/span span style="color: #333333"||/span (j span style="color: #333333">= 0 && arr[i] == pat[j])) i++, j++;
if(arr[i] != pat[j]) j = pi[j];
if(j == m) {
printf("The matching %d\n",i-m+1);
j = pi[j];
}
}
}

2.4 Rabin-Karp string search algorithm

앞에 설명했던 문자열 알고리즘이 단순한 문자 자체를 비교하는 알고리즘이었다면, 라빈 카프 알고리즘은 해시를 이용하여 해시끼리 비교하는 알고리즘이다. 우선 찾으려는 패턴의 해시값을 구한다. 그리고 문자열의 앞에서부터 뒤에서까지 해시 값을 이동시킨다. 이때 mod 연산을 사용하므로 앞에서 [math]26^{m-1} \times p \enspace mod \enspace q[/math]를 뺀 뒤, 그 값에다가 26을 곱하고 다시 mod 연산을 취한 뒤, 뒤에 자리를 더한다. 위의 수식은 알파벳 소문자만 고려했을 경우만 계산한다.

라빈-카프는 문자열이 매우 커질 경우 해시 충돌이 일어날 가능성이 커지므로 상당히 불안정하고 비효율적이다. 하지만 현실세계에서의 문자열은 1억자리 이상 넘어가는 경우는 드물다. 또한 KMP 보다 빠른 경우가 존재한다. 해시를 사용하므로 시간 복잡도는 평균적으로 O(n+m)이다.

아래 코드는 [math]26^{m-1} \enspace mod \enspace q[/math]를 미리 구해놓는다. 왜냐하면 [math]((26^{m-1} \enspace mod \enspace q) \times (p \enspace mod \enspace q)) \enspace mod \enspace q \equiv 26^{m-1} \times p \enspace mod \enspace q[/math]이므로 매번 구하지 않아도 되므로 매우 효율적이다. 정수론을 배웠다면 혹은 간단하게 접해봤다면 쉽게 이해할 수 있을 것이다.

2.4.1 코드

#define mod 1000000009
long long make_hash_p(char str[], int _size) {
int i;
long long hash_p = 0;
for (i = 0; i < _size; i++) {
hash_p *= 26;
hash_p += str[i];
hash_p %= mod;
}
return hash_p;
}
void match_s(char str[], int _size, int _size_p, long long hash_p) {
int i;
long long hash_s = 0;
long long last = 1;
for (i = 0; i < _size_p; i++) {
hash_s *= 26;
hash_s += str[i];
hash_s %= mod;

if (i == _size_p - 1) continue;
last *= 26;
last %= mod;
}
for (i = _size_p; i <= _size; i++) {
if (i >= _size_p) {
if (hash_s == hash_p) printf("match %d\n", i - _size_p + 1);
if (i == _size) break;

hash_s -= last * str[i - _size_p];
hash_s *= 26;
hash_s += str[i];
hash_s %= mod;
if (hash_s < 0) hash_s += mod; //빼는 과정에서 해시값이 음수가 되는 경우를 방지
}
}
}

3 최장 공통 부분 문자열 알고리즘(Longest Common Substring Algorithm)

두 문자열이 주어졌을 때, 최장 공통 부분 문자열을 찾는 알고리즘이다. 생명과학 분야가 발전함에 따라 어떤 두 개의 염기 서열을 비교해야 하는 상황이 많이 나타났기 때문에 각종 알고리즘이 나온 분야이기도 하다.

3.1 Dynamic Algorithm

다이나믹 알고리즘으로 푸는 방법이 제일 잘 알려진 방법이다. 두 문자열을 이용해서 일정한 규칙의 테이블을 만든 후, 그 테이블을 살펴보면서 최장 공통 부분 문자열을 찾아낼 수 있다. 이 경우 테이블에 따라 계산하므로 시간 복잡도는 [math]O(n^2)[/math]이다.

다이나믹 프로그래밍은 아래와 같은 과정을 거친다.

다음 공식에 맞춰서 표를 생성한다.
- 0 ≤ i ≤ len(A)이고 0 ≤ j ≤ len(B)일 때,
  - A[i] == B[j]일 경우 LCSTable(i, j) = LCSTable(i - 1, j - 1) + 1
  - 아닐 경우 LCSTable(i, j) = 0
표에서 가장 큰 숫자를 확인한다.
- A = BCBBBC, B = CBBBCC 인 경우

		B	C	B	B	B	C
	0	0	0	0	0	0	0
C	0	0	1	0	0	0	1
B	0	1	0	2	1	1	0
B	0	1	0	1	3	2	0
B	0	1	0	1	2	4	0
C	0	0	2	0	0	0	5
C	0	0	0	0	0	0	1

3. 이 숫자들은 공통 부분 문자열의 길이를 나타내는 것으로, 대각선으로 왼쪽 위로 올라가면서 해당 문자를 확인해보게 되면 실제 최장 공통 부분 문자열, 즉 Longest Common Substring을 찾을 수 있다. 위의 표에서 가장 큰 것은 5이므로, 대각선으로 올라가면서 문자를 확인해보면 "CBBBC"가 최장 공통 문자열임을 확인할 수 있다.

4. ~~???~~

5. ~~PROFIT!~~

3.1.1 코드

void find() {
int i, j;
int max1 = 0, tmpi = 0;

for(i = 1; i

3.2 Suffix Array + LCP Array

위에 다이나믹 알고리즘의 시간 복잡도 [math]O(n^2)[/math]는 실제 자연에서 볼 수 있는 염기 서열의 길이를 생각해보면 매우 오래 걸릴 뿐더러, 메모리 낭비 역시 심하다. 수많은 컴퓨터 과학자들과 수학자들이 이 문제에 대해 매달려 왔으며, 이에 대한 해결법 중 하나가 Suffix Array(Suffix Tree를 대체하기 위해 만들어진 배열)를 활용하는 방법이었다.
비교하고자 하는 두 문자열을 합한 뒤, 그 문자열의 Suffix Array를 구했다면 LCP Array를 O(n)만에 구할 수 있다. 이 때의 LCP Array를 이용하여 최대 공통 부분 문자열을 찾아낼 수 있다. 이 때의 탐색과 LCP Array를 만드는 데 걸리는 시간 복잡도는 O(n)이므로 Suffix Array를 구하는 시간 복잡도에 따라서 성능이 좌우된다.

3.2.1 코드

//Suffix Array 및 LCP Array 생성
bool cmp(int a, int b) {

if(o[a] != o[b]) return o[a]

이 경우의 시간 복잡도는 [math]O(n \log^2 n)[/math]이다.

4 다중 패턴 매칭

4.1 Aho-Corasick Algorithm

KMP 알고리즘과 Trie 를 결부한 형태의 알고리즘이다. Trie와 KMP를 모두 이해하고 있는 상태여야만 이 알고리즘을 이해할 수 있다. 추가로 BFS역시 알고있어야 한다. 상태 전이 함수(혹은 실패함수, Failure function)가 존재한다.

KMP와 Trie, BFS에 대해서 알고있다는 가정 하에 서술하면. Aho-Corasick은 KMP를 Trie 에서 수행하는 것이다. 다만 다른점은 노드에서 실패할 경우 다른 노드로 이동한다. 비교하고자 하는 노드 i, failure function을 기록할 노드 j 가 존재한다고 할때, i와 j 둘다 다음 상태로 이동 할 수 있다면 이동한다. 그리고 failure function에 기록한다. 만약 이동할 수 없다면 failure function을 사용할 수 없을때 까지 혹은 다음 상태로 이동 할 수 있을 때 까지 failure function을 통해 i를 전이 시킨다. 만약 이 과정을 DFS로 수행한다면? 어떤 문자열 집합에 있는 모든 문자열이 아닌 단일 문자열에 대한 failure function만 생성하게 될것이다. 하지만 BFS의 경우는 노드 i에서의 prefix 길이는 노드 j에서의 prefix 길이보다 짧다는 것이 자명하기 때문에 모든 failure function을 생성하게 된다.

이 경우의 시간 복잡도는 [math]O(n+m+p)[/math] 가 된다. 여기서의 n은 문자열의 길이, m은 트라이의 노드 개수, p는 패턴 발생 횟수이다. 이때 p는 사용 방법에 따라 상수 취급할 수 있다. 만족하는 패턴 하나만 찾으면 되는 경우가 여기에 속한다.

주의 할 점은 failure function을 만드는 과정에서 노드 i와 j가 다음상태로 이동하는 도중에 노드 i가 문자열 집합 내에 존재하는 문자열임을 알릴 때 노드 j는 그 문자를 포함하는 것이니 노드 j역시 문자열 집합 내에 존재하는 문자열을 포함함을 알린다. 보통 동적 배열을 사용하여 처리한다.
아래 코드는 동적 배열을 이용하여 어떤 패턴이 속하는지 알리지 않고 어떤 패턴이 그 문자열에 속한다 정도만 판별 할 수 있는 코드이다.

아래 코드는 영어 소문자만을 고려하며, array로 Trie를 만든 경우이다.
또한 해당 코드는 어떤 문자열 s에 대해 문자열 집합 P이 하나라도 속하면 true를 반환한다.
Trie 만드는 방법은 해당 항목 참조

4.1.1 코드

struct node {
int i;
int j;
};
queue<node> q;
// failure function 생성
void make_fail(int trie[][26], int fail[], bool chk[]) { // trie - 트라이, fail - 상태전이 함수, chk - 문자열 존재 여부
node tmp, now; // now = 현재 위치를 담는 node, tmp = 보조 node (갱신 등)
tmp.i = -1;
tmp.j = 0;
q.push(tmp);
while (q.size()) {
now = q.front();
q.pop();
for (k = 0; k < 26; k++) {
tmp = now;
if (trie[tmp.j][k] == 0) continue; // j에 대해 다음 노드로 이동 할 수 없다면 
while (1) {
if (tmp.i == -1 || (tmp.i != -1 && trie[tmp.i][k] > 0)) { // i에 대해 다음 노드로 이동 가능하거나, failure function을 사용할 수 없다면
if (tmp.i == -1) tmp.i = 0;
else tmp.i = trie[tmp.i][k];
tmp.j = trie[tmp.j][k];
fail[tmp.j] = tmp.i;
if (chk[tmp.i] == true) chk[tmp.j] = true;
q.push(tmp);
break;
}
else tmp.i = fail[tmp.i]; // i에 대해 다음노드로 이동이 불가능 하고, failure function을 사용할 수 있다면
}
}
}
}
bool match(char s[], int tire[][26], int chk[]) { //문자열 s
int i = 0, j = 0;
while (1) {
if (j == n) break;
nxt = s[j] - 'a'; // 다음 상태로 이동하기 위한 문자 nxt
if (i == -1 || (i != -1 && trie[i][nxt] > 0)) { // i가 더 이상 failure fuction을 방문하지 못하게 되거나, 혹은 다음 상태로 이동이 가능하면
if (i == -1) i = 0;
else i = trie[i][nxt];
j++;
}
else i = fail[i]; // i가 failure function을 방문 가능하며, 다음 상태로 이동 불가능할때
if (i != -1 && chk[i]) return true;
}
return false;
}

↑ 한국어 같은 영어가 아닌 언어 또는 특수 문자들
↑ 참고로 라이브러리에서 제공하는 문자열 찾기 함수에서 사용하는 알고리즘은 보통 KMP 알고리즘보다 느리다. by 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 2권

[1] 한국어 같은 영어가 아닌 언어 또는 특수 문자들

[2] 참고로 라이브러리에서 제공하는 문자열 찾기 함수에서 사용하는 알고리즘은 보통 KMP 알고리즘보다 느리다. by 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 2권

[1]

[2]

		B	C	B	B	B	C
	0	0	0	0	0	0	0
C	0	0	1	0	0	0	1
B	0	1	0	2	1	1	0
B	0	1	0	1	3	2	0
B	0	1	0	1	2	4	0
C	0	0	2	0	0	0	5
C	0	0	0	0	0	0	1

		B	C	B	B	B	C
	0	0	0	0	0	0	0
C	0	0	1	0	0	0	1
B	0	1	0	2	1	1	0
B	0	1	0	1	3	2	0
B	0	1	0	1	2	4	0
C	0	0	2	0	0	0	5
C	0	0	0	0	0	0	1