2021. 1. 31. 03:44ㆍ알고리즘/알고리즘 정리
1. 문자열
현대의 컴퓨터의 많은 양의 데이터들은 거의 문자열이다.
때문에 문자열을 다루는 문제와 자료 구조는 전산학의 중요한 연구 주제이다.
문자열 검색 문제를 위한 kmp알고리즘과
문자열 처리의 스위스 칼이라고 할 수 있는 자료 구조 접미사 배열(suffix array)에 대해 알아보자.
- 문자열 = S
- 문자열의 길이 = |S|
- 문자열 S의 i 번 = S[i]
- 부분 문자열(substring) = S[i,..j]
- 접두사(prefix) = 0번부터 특정 문자까지의 문자열 S[0..a]
- 접미사(suffix) = 특정 문자에서 부터 끝까지의 문자열 S[b...]
2. 단순한 문자열의 검색
문자열이 A, B가 있을 때
문자열 A가 문자열 B의 부분 문자열로 포함하는지 확인하고
부분 문자열의 시작 위치들을 반환하는 알고리즘을 생각해보자
이 알고리즘을 구현하는 단순한 방법은 B의 가능한 모든 시작 위치를 다 시도하도록 짜는 것이다.
vector<int> naiveSearch(const string& A, const string& B)
{
vector<int> ret;
for(int begin = 0; begin + B.size() <= A.size(); ++begin)
{
bool matched = true;
for(int i = 0; i < B.size(); i++)
if(A[begin + i] != B[i])
{
matched = false;
break;
}
if(matched) ret.push_back(begin);
}
return ret;
}
이 알고리즘은 다음과 같은 입력일때 비효율적이다.
- 모두 똑같을 때 시작 위치 수는 |A| 가 되어 전체 시간복잡도는 O(|A||B|) 가 된다.
단순한 알고리즘은 구현이 단순하다는 장점이 있기 때문에
표준라이브러리의 구현에 널리 사용된다.
c: strstr()
c++: string::find()
java: indexOf()
3. kmp 알고리즘 (knuth-moris-pratt)
문자열 A에서 B를 포함하는 부분 문자열이 시작하는 인덱스를 찾는 알고리즘
총 O(|A| + |B|)의 수행시간이 걸린다.
부분 일치 테이블(partial match table) : 실패 함수(failure function)
kmp 알고리즘의 핵심은 패턴 분석이다.
B의 패턴을 분석해서 A와 비교해나가면 중복된 계산을 없앨 수 있다.
ababc 인 B가 주어지면 다음과 같이 분석할 수 있다.
| index | -1 | 0 | 1 | 2 | 3 | 4 |
| B | a | b | a | b | c | |
| failure | -1 | -1 | 0 | 1 | -1 |
index = -1 : failure 배열을 사용하기 위해서 임의로 만든 인덱스 번호.
failure 배열을 구성함에 있어서 이전 인덱스의 정보가 필요하고,
인덱스 0 과 동등한 문자와 패턴을 처음으로 돌리는 문자를 구분 짓기 위해 -1을 사용하였다.
여기서 failure라는 배열의 의미는 다음과 같다.
failure[i] = -1 : i 인덱스로 인하여 접두사 B[0... i-1]에서 이전 문자 B[i-1]까지 이어오던 패턴이 망가짐을 의미한다.
패턴이 망가졌으므로 i이후는 다시 B[0]부터 패턴이 반복되는지 확인해야한다는 것을 의미한다.
failure[i] >= 0 : b[i] 와 b[failure[i]] 는 같은 문자이고, 같은 패턴의 같은 위치임을 의미한다.
failure[i-1]가 0이상일 경우 b[i-1] 또한 b[failure[i-1] 와 같다.
즉 failure 의 값은 연속되어있고
failure가 0~n 의 값을 가지는 구간은
B의 0 부터 n번째 인덱스의 반복된 패턴임을 의미한다.
failure 가 오름차순이 아닌 경우:
B: zxczxxfzxczxczxxf
검은색 zxc 부터 failure배열은 다음과 같다. 01234 23456
여기서 12번째 문자 C의 failure 값은 다음과 같이 결정된다.
- failure[11] = 4
- failure[4] = 1
- B[1] = X
- B[2] = C
- B[11] = X
- B[12] = C
- B[failure[failure[11]] + 1] == B[12]
=> failure[12] = failure[4] + 1
12번째 인덱스에서 패턴이 망가졌지만, 앞의 패턴 일부를 되살릴 수 있음을
이전 인덱스를 통해 알 수 있다.
또한 이전 인덱스를 failure를 합성함수로써 계산하면
이후 문자가 패턴에 속해있는지 검사할 수 있음을 알 수 있다.
코드는 다음과 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void failureFunction(char* B, int* failure)
{
int n = strlen(B);
failure[0] = -1;
for(int start = 1; start < n; start++)
{
int before = failure[start-1];
while(B[before+1] != B[start] && (before >= 0))
before = failure[before];
if(B[before+1] == B[start]) failure[start] = before +1;
else failure[start] = -1;
}
}
|
cs |
실제 문자열 검색의 구현
이제 failure 함수로 생성한 failure 배열을 가지고 부분 문자열을 찾아보자
문자열 A와 B를 가리키는 인덱스 각각을 i 와 j라고하자.
A와 B의 처음 인덱스는 각각 0 이다.
반복문을 통해 A의 인덱스 i가 A의 끝까지 탐색할때까지 반복하자.
만약 A[i] == B[j] 라면
i와 j를 같이 증가시킨다.
만약 j가 1 이상인데 A[i] != B[j]라면
i는 그대로 두고
j= failure[j-1]+1 로 업데이트 시켜
패턴이 유지 되는지 확인한다.
유지되지 못할 경우 j = 0 이 되어 처음부터 검사하게 된다.
전체 코드는 다음과 같다. 이 코드는 C언어로 구현했기 때문에
동적배열을 만들고 모든 부분 문자열을 담아 반환하는 함수를 구현하기 힘들어 간단하게
첫 부분 문자열의 시작점을 반환하게 구현하였다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void failure(char* B, int* failure)
{
int n = strlen(B);
failure[0] = -1;
for(int start = 1; start < n; start++)
{
int before = failure[start-1];
while(B[before+1] != B[start] && (before >= 0))
before = failure[before];
if(B[before+1] == B[start]) failure[start] = before +1;
else failure[start] = -1;
}
}
int kmpSearch(char* A, char* B, int* failure)
{
int i = 0, j = 0;
int n = strlen(A), m = strlen(B);
while(i < n && j < m)
{
if(A[i] == B[j])
{
i++; j++;
}
else if(j == 0)
i++;
else
j = failure[j-1] + 1;
}
return (j < m) ? -1 : (i - m);
}
int main()
{
char* A = "abcdefghijk";
char* B = "cde";
int* F = (int*)malloc(strlen(B));
failure(B, F);
printf("%d\n", kmpSearch(A, B, F));
}
|
cs |
부분 합과 kmp 알고리즘 나의 생각
kmp 알고리즘과 부분 합의 유사한 점이 있다
바로 공통된 부분 즉, 이미 얻은 정보를 사용하는 것이다.
kmp 알고리즘에서는
i번 째 문자에서 j개를 검사하고 j+1에서 불일치가 발생하게 되면
전처리된 failure값을 통해 i+1에서 다시 검사를 시작 하지 않고
j+1에서부터 검사를 시작한다.
부분합 문제에서도 마찬가지로
전처리된 psum값으로 공통된 부분을 제거하여
모든 부분 합을 O(1)만에 계산할 수있는 것,
크리스 마스문제 에서 이전에 계산했던 정보로 문제를 해결하는것이다.
4. 알고리즘 문제해결전략에서의 kmp알고리즘
접미사와 접두사
알고리즘 문제해결전략에서는
kmp알고리즘을 접두사와 접미사를 이용하여 설명하였다.
문자열 B를 문자열 A에서 찾을 때
A의 begin 부터 시작하여 matched길이만큼 B와 일치하고
matched+1에서 불일치가 되었다고 가정해보자.
길이가 matched인 접두사 B[...matched-1]는
현재 A의 부분문자열 A[begin, ... begin + matched-1]과 일치한 상태이다.
여기서 우리의 목적은 begin+1에서부터 조사하는것을 피하는것이다.
이것을 피하는 방법은
부분 문자열 B[k ... matched -1] 와 접두사 B[...matched-k -1] 가 일치하는
k를 찾는 것이다.
(접두사 B[..matched-1] 안에서 동일한 패턴인 접미사와 접두사의 길이가 matched - k인 k를 찾는다.)
k를 찾게되면 A[begin + k ... begin + matched - 1] 역시
B와 matched - k길이만큼 일치하게 된다.
( A[begin,... begin + matched -1] 은 B[...matched -1] 와 동일하기 때문이다.)
즉, begin +1 에서 처음부터 조사하는 것이 아니라
begin + k 에서부터 B[matched - k-1] 이후 부터 조사하는 것이다.
부분 일치 테이블
접미사와 접두사가 같은 문자열의 길이 matched - k의 최대값을 저장하는 배열을
pi라는 배열에 전처리하면 탐색에서 불일치시에 바로 다음 조사할 곳으로 갈 수 있다.
pi[i] = B[... i] 의 접두사도 되고 접미사도 되는 최대 길이를 반환
이 pi라는 배열은 위에서 다루었던 failure 배열과 동일한 역활을 하지만.
이것은 '길이'를 저장하여 다르게 표현한 것이다.
pi를 계산하기위한 알고리즘은 B 에서 B를 찾는 문제와 똑같다.
B[1] 에서 부터 B[0]과 비교하면서 이 값이 동일하면 다음 문자를 비교해나간다.
즉, B[begin + matched] 와 B[matched]를 비교하는 것이다.
- pi 를 0으로 초기화 한다.
- 두 변수 begin 과 matched 를 생성한다.
- begin 은 현재 조사하고 있는 B의 인덱스
(begin 의 초기값은 1이다 0일시 B와 B를 비교하는것이므로 항상 동일하다)
- matched 는 begin에서부터 일치가 계속된 현재 비교하고 있는 인덱스 이다.
또한, 이전의 길이를 나타내준다.
- 만약 B[begin + matched] == B[matched] 일 때
- pi[begin + matched] = matched + 1;
- matched++;
- matched 번째가 추가 됨으로써 pi[begin + matched]에 증가된 길이를 저장하고,
- matched 가 다음번 인덱스를 가리킴.
- 그외의 경우
- matched가 0일시 겹치는 부분이 없으므로 시작점을 다음 인덱스로 옮겨서 비교한다.
- matched가 끊어지는 경우 matched -1 까지는 일치함
- begin += matched - pi[matched -1];
- matched = pi[matched-1];
- 따라서 접미사랑 똑같은 접두사를 붙이기 위하여 현재 길이에 이전 pi를 뺀다.
- matched는 접미사랑 동일한 접두사의 길이가 되어 다음 인덱스를 가리킨다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
//접두사와접미사가 같아야한다
//n의 각 접두사에대해 접두사도 되고
//접미사도 되는 문자열의 최대길이를 계산
//pi[i] = N[... i] 의접두사도되고접미사도되는문자열의최대길이
//pi는 N이 어디까지 일치했는지가 주어질 떄 다음시작위치를ㅇ어디로해야할지를말해준다
vector<int> getPartialMatch(const string& N)
{
int m = N.size();
vector<int> pi(m, 0);
int begin = 1, matched = 0;
//matched = 현재 일치된 글자수
while (begin + matched < m)
{
if (N[begin + matched] == N[matched])
{
matched++;
pi[begin + matched - 1] = matched;
}
else
{
if(matched == 0)
begin++;
else
{
begin += matched - pi[matched -1];
matched = pi[matched-1];
}
}
}
return pi;
}
|
cs |
kmpSearch 다음 시작 위치 찾기
위의 알고리즘과 다른점은 B와 B를 비교하는게 아니라 A에대해 B를 조사하는 것이다.
다른점은 begin = 0 에서 시작하고,
matched가 B의 길이와 같으면 인덱스를 동적배열에 담는것이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
vector<int> kmpSearch(const string& H, const string& N)
{
int n = H.size(), m = N.size();
vector<int> ret;
vector<int> pi = getPartialMatch(N);
int begin = 0, matched = 0;
while(begin <= n - m)
{
if(matched < m && H[begin + matched] == N[matched])
{
matched++;
if(matched == m) ret.push_back(begin);
}
else
{
if(matched == 0)
begin++;
else
{
begin+=matched - pi[matched - 1];
matched = pi[matched -1];
}
}
}
return ret;
}
|
cs |
kmp 알고리즘의 다른 구현
책에서는 또 다른 구현을 소개하였는데
이것은 위에 구현했던 실패함수와 유사하다는 것을 알 수 있다.
여기서 i 의 의미는 begin + matched 와 같기 때문에
사실 위의 구현과 다른 차이점은 없다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
vector<int> kmpSearch2(const string& H, const string& N)
{
int n = H.size(), m = N.size();
vector<int> ret;
vector<int> pi = getPartialMatch(N);
int matched = 0;
for(int i = 0; i < n; i++)
{
while(matched > 0 && H[i] != N[matched])
matched = pi[matched -1];
if(H[i] == N[matched])
{
matched++;
if(matched == m)
{
ret.push_back(i-m+1);
matched = pi[matched -1];
}
}
}
return ret;
}
|
cs |
kmp 알고리즘을 이용한 환형 시프트 연산
|
1
2
3
4
|
int shifts(const string& original, const string& target)
{
return kmpSearch(original + original, target)[0];
}
|
cs |
shifts(original, target) = 문자열 original을 target으로 만들기 위해 환형 시프트를 몇전이나 해야하는지
즉 shifts(a,b)는 a에서 몇 칸을 반시계 방향으로 돌려야 b를 얻을 수 있는지 알 수 있다.
shifts(b,a)는 a에서 시계방향으로 몇 칸을 돌리는지를 반환한다.
5. 접미사 배열
접미사 배열은 문자열 알고리즘에서 대부분 쓰인다.
접미사 배열은 아주 간단한 자료 구조로
어떤 문자열 S의 모든 접미사를 사전순으로 정렬해 둔 것이다.
(메모리 효율을 위해 대개 정수배열로 시작 위치 인덱스만 저장한다)
| i | A[i] | S[A[i]...] |
| 0 | 8 | a |
| 1 | 0 | alohomora |
| 2 | 3 | homora |
| 3 | 1 | lohomora |
| 4 | 5 | mora |
| 5 | 2 | ohomora |
| 6 | 4 | omora |
| 7 | 6 | ora |
| 8 | 7 | ra |
접미사 배열을 이용한 검색
문자열 H가 문자열 N을 포함한다면 항상 N은 H의 어떤 접미사의 접두사라는점을 이용한다.
이 속성을 이용하면 H의 접미사 배열을 이진 탐색해서
각 문자열이 출현하는 위치를 찾을 수 있다.
접미사 배열의 길이는 항상 |H|이므로, 이진 탐색의 내부는 O(lg|H|)번 수행된다.
각 문자열 비교에 O(|N|) 시간이 걸리기 때문에
전체 수행시간은 O(|N|lg|H|)이된다.
같은 문자열에서 다른 문자열들을 찾을 때 효율적이다.
접미사 배열의 생성
접미사 배열을 만드는 가장 간단한 방법은 일반적인 정렬 알고리즘을 사용하는 것이다.
문자열의 길이가 n일 때, [0, n-1] 범위의 정수를 모두 담은 정수 배열을 정렬하되,
두 정수를 비교할 때 해당 위치에서 시작하는 접미사들을 비교한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
struct SuffixComparator
{
const string& s;
SuffixComparator(const string& s) : s(s) {}
bool operator()(int i , int j) {
//strcmp대신 s.substr()을사용하게되면 임시객체를만드는비용이 생긴다
return strcmp(s.c_str() + i , s.c_str() + j) < 0;
}
};
vector<int> getSuffixArrayNaive(const string& s)
{
vector<int> perm;
for(int i = 0; i < s.size(); i++) perm.push_back(i);
sort(perm.begin(), perm.end(), SuffixComparator(s));
return perm;
}
|
cs |
위 코드의 시간 복잡도는 O(n^2lgn)이다.
하지만 문자열을 비교할 때 대부분 앞의 글자에 의해 판단되므로
'생각'보다 빨리 수행될 것이다.
맨버-마이어스의 알고리즘: 접미사 배열 생성
접미사 배열을 생성하는 가장 빠른 알고리즘의 시간 복잡도는 n이다.
맨버-마이어스 알고리즘은 가장 빠르지는 않지만 구현이 간편한 알고리즘이다.
이 알고리즘은 접미사들의 목록을 여러 번 정렬하는데, 매번 그 기준을 바꾼다.
처음에는 접미사 첫 한 글자만을 기준으로 , 다음에는 접미사 첫 두 글자를 기준으로
그 다음에는 접미사의 첫 네 글자를 기준으로,
이렇게 lgn번의 정렬을 반복하면 접미사 배열이 생성된다.
이렇게 2의 지수승으로 글자를 나누는 이유는
2^n = (2^(n-1) + 2^(n-2) +... 1) + 1
이 식이 성립하는 이유와 같다. 밑에서 자세히 살펴보도록하자
아무튼 이런 이전 정렬에서 얻은 정보를 이용하여 O(1)만에 대소비교가 가능해진다.
nlgn 을 lgn번 반복하므로 O(n lgn lgn) 의 수행시간을 가진다.
group[i] = S[i...] 가 속한 그룹의 번호
정렬한뒤 각 접미사에 첫글자가 같은것 끼리 그룹 번호를 부여한다.
이를 위한 비교자는 다음과 같다.
struct Comparator {
const vector<int>& group;
int t;
Comperator(const vector<int>& _group, int_t): group(_group), t(_t)
{ group = _group; t = _t; }
//a가 b보다 앞에올 조건
bool operator(int a, int b) {
if(group[a] != group[b]) return group[a] < group[b];
return group[a+t] < group[b+t];
}
};i + t 글자 비교
t 글자를 기준으로 각 접미사를 그룹에 배정한 뒤, 이 정보를 이용해 2t글자를 기준으로 정렬하는 과정을 정리 해보았다.
|
- t = 1
초기 group은 접미사의 첫글자를 가지고 있는 간단한 그룹이다. (아스키 코드값-알파벳 대소비교는 잘 작동한다)
초기 perm은 0 ~ n 까지 길이순으로 정렬되어있이며 같은 길이는 없다.
perm 을 Comparator로 '같은 단계' 인 접미사를 비교하면 앞글자가 아니라 그 다음글자 (t=1이므로) 를 비교한다.
만약 그 다음 글자부터 "그룹이 바뀐다면" 그 그룹에 따라 앞에 올것인지 뒤에 올것인지를 알 수 있다.(사전순) 이로인해 정렬이 끝난 후 그룹을 나눌 수 있게 된다, (group[n] = -1 이므로 n-1번째인덱스는 항상 같은 그룹의 맨앞에 위치하게 된다.)
정렬이 끝난 후 group을 새롭게 구성한다.
group을 구성할 때 중요한 것은 compareUsing2T(perm[i-1], perm[i]) 을 이용하여 '참' 일때 그룹을 쪼개는 것이다. '참' 일때는 이전 그룹이 다를 경우와 "같은 그룹에서 다음글자(+ t)부터 그룹이 달라질 때" 두가지 경우다.
따라서 정렬할때 앞으로 옮긴 것들은 전부 그룹에서 나와 별도의 그룹을 만든다. 또 경계값을 침범한 n-1번째 인덱스는 독립 그룹을 만들고 다른 것은 다른 그룹을 생성한다. 이로인해 n-3번째 인덱스는 별도의 그룹을 만들 여지가 생기게 된것이다.
- t = 2
compareUsing 비교자를 새로운 group과 t 로 업데이트 시킨다.
perm을 다시 업데이트된 비교자로 비교하게 되면 같은 그룹에 있는 것들은 이전의 t 즉, 1 이하는 전부 앞에서 별도의 그룹을 만든 것을 알 수 있다. 따라서 이제 t를 더해서 n+1이상이 나올 접미사는 없다는 것을 알 수 있다.
group을 업데이트 해보자, 그럼 n-2 또한 경계값을 침범하므로 별도의 그룹을 만들게 된다. 또한 t=1 일때 n-1의 독립 그룹이 생겼으므로 n-3 또한 별도의 그룹을 만들게 된다.
이제 감이 올것이다, 앞에서 별도의 그룹을 만들어가면 이 그룹들로인해 대소비교가 명확해지는 인덱스들이 생긴다는 것을 볼 수 있다.
- t = 4
group의 업데이트만을 보자, 앞에서 1~3의 길이들은 독립 그룹을 생성하였으므로 4~7의 길이를 가진 접미사 또한 독립 그룹을 생성할 것이다. 따라서 2^n 길이의 접미사배열을 만들려면 위 계산을 n번 수행해야한다.
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
struct Comparator {
const vector<int>& group;
int t;
Comparator(const vector<int>& _group, int _t): group(_group), t(_t) {}
bool operator ()(int a, int b) {
if(group[a] != group[b]) return group[a] < group[b];
return group[a+t] < group[b+t];
}
};
vector<int> getSuffixArray(const string& s)
{
int n = s.size();
int t = 1;
vector<int> group(n+1);
for(int i = 0; i < n; i++) group[i] = s[i];
group[n] = -1;
vector<int> perm(n);
for(int i = 0; i < n; i++) perm[i] = i;
while(t < n)
{
Comparator compareUsing2T(group, t);
sort(perm.begin(), perm.end(), compareUsing2T);
t*=2;
if(t>=n) break;
vector<int> newGroup(n+1);
newGroup[n] = -1;
newGroup[perm[0]] = 0;
for(int i = 1; i < n; i++)
{
if(compareUsing2T(perm[i-1], perm[i]))
newGroup[perm[i]] = newGroup[perm[i-1]] + 1;
else
newGroup[perm[i]] = newGroup[perm[i-1]];
}
group = newGroup;
}
return perm;
}
|
cs |
- 보이어 무어 알고리즘
- 접미사 트리: 접미사 배열과 비슷하지만 더 빠른 검색
- 버킷 정렬을 이용하면 앞에서 구현한것 보다 더 빠른 접미사 생성 알고리즘을 구현할 수 있다.(nlgn)
- 두 접미사가 공유하는 최대 길이 접두사를 찾아야하는 경우 두 접미사를 직접 비교하는 알고리즘이 필요하다
이는 "linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Application"
O(|N| + lg|H|)
- 알고리즘 문제해결전략 643p
- Fundamentals of Data Structures in C 97p
'알고리즘 > 알고리즘 정리' 카테고리의 다른 글
| [트리] Tree 2: 이진 검색 트리, 트립 (0) | 2021.02.04 |
|---|---|
| [트리] Tree 1: 트리의 구현, 순회 (0) | 2021.02.04 |
| 큐와 스택 그리고 데크 (0) | 2021.01.29 |
| [선형 자료 구조] 동적 배열과 연결 리스트 (0) | 2021.01.29 |
| [부분 합] Partial sum (0) | 2021.01.28 |