Suffix Array O(NlgNlgN)과 O(NlgN) 구현 및 설명.

< Suffix Array O(NlgNlgN)과 O(NlgN) 구현 및 설명 >

최근 입사 동기가 물어본 일도 있고 해서 정리를 해봤다.

먼저 어떤 스트링(문자열)의 Suffix Array를 구한다는 것이 무슨 뜻인지부터 살펴보자.

결론부터 얘기하자면, mississipi란 스트링이 주어졌을 때 Suffix Array라는 것을 구하면 9741086352가 되겠다.

이제 조금씩 살펴보자.

어떤 string의 suffix라는 것은 접미사를 의미한다.

mississipi란 string에는

[0] mississipi

[1] ississipi

[2] ssissipi

[3] sissipi

[4] issipi

[5] ssipi

[6] sipi

[7] ipi

[8] pi

[9] i

이렇게 위와 같이 10가지 suffix가 있을 것이다.

해당 suffix들을 사전순으로 정렬하면 다음과 같다.

[9] i

[7] ipi

[4] issipi

[1] ississipi

[0] mississipi

[8] pi

[6] sipi

[3] sissipi

[5] ssipi

[2] ssissipi

이 순서가 바로 Suffix Array이다.

즉, 접미사 배열(Suffix Array) = 한 문자열(a string)의 접미사들을 모두 모아 정렬했을 때, 그 순서를 문자열의 index로만 표현한 배열이라 할 수 있다.

그럼 이걸 어떻게 구할까?

가장 무식한 방법은 문자열 길이 N만큼 Suffix들을 따로 저장한 다음 sorting 해버리는 것이다.

코드로 구현하면 다음과 같다.

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
//suffix array: bruteforce O(N^2lgN)
#include <string>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<string, int> psi;
vector<int> getsfx(string &s) {
    int n=s.size();
    vector<psi> v;
    for(int i=0; i<n; i++) {
        v.emplace_back(psi(s.substr(i),i));
    }
    sort(v.begin(), v.end());
    vector<int> ans;
    for(int i=0; i<n; i++) {
        ans.emplace_back(v[i].second);
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    string s; cin >> s;
    vector<int> sfx = getsfx(s);
    for(auto x: sfx) cout << x << " ";
    return 0;
}
Colored by Color Scripter
cs

Suffix를 옮겨담는데만 O(N^2)시간이 걸리고, sorting은 문자열 sorting이므로 O(N^2lgN)시간이 걸린다.

결과적으로 O(N^2lgN)시간이 걸리고, 문자열길이 N값이 10,000만 되더라도 엄청난 성능저하가 기대된다.

그럼 알고리즘을 개선시켜 조금 빠른속도인 O(NlgNlgN)에 구해보자.

이 방법은 Suffix Array를 구하고자 하는 문자열 하나를 길이 1,2,4,8,16,...단위로 확인하면서 그룹을 지어주는 것이다.

이 말만 들으면 이 블로그를 찾아온 보람이 없다.

좀 더 디테일하게 알아보자.

mississipi를 길이 1단위로 그룹을 지어보자. 그룹은 사전순서로 작은 부분문자열에 작은 숫자를 부여하는 것이다.

index	0	1	2	3	4	5	6	7	8	9
string[index]	m	i	s	s	i	s	s	i	p	i
g[index]	2	1	4	4	1	4	4	1	3	1

각 부분문자열을 1개 길이 단위로 봤으므로 결국 '문자'만 보고 몇 번째에 해당하는지 g[index]에 적어주었다.

i값이 사전순으로 가장 빠르므로 1이고, m은 2, p는 3, s는 4이다.

이제 2개 길이 단위로 g[index]를 구해보자.

일단 결과를 보면 아래와 같다.

index	0	1	2	3	4	5	6	7	8	9
string[index]	m	i	s	s	i	s	s	i	p	i
g[index]	4	3	7	6	3	7	6	2	5	1

2개 길이 단위로 본다는 것은, string[0..1], string[1..2], string[2..3], .. 값들을 비교하겠다는 뜻이다.

다시 말해서,

[0]: string[0..1]: mi

[1]: string[1..2]: is

[2]: string[2..3]: ss

[3]: string[3..4]: si

[4]: string[4..5]: is

[5]: string[5..6]: ss

[6]: string[6..7]: si

[7]: string[7..8]: ip

[8]: string[8..9]: pi

[9]: string[9..10]: i* (존재하지 않는 문자를 *로 표시했다.)

위와 같은 부분문자열을 정렬해서 순서대로 그룹번호를 지정하겠다는 뜻이다.

위의 부분문자열(substring)들을 정렬해보면 다음과 같다.

[9]: string[9..10]: i* => 1번째

[7]: string[7..8]: ip => 2번째

[1]: string[1..2]: is => 3번째

[4]: string[4..5]: is => 3번째

[0]: string[0..1]: mi => 4번째

[8]: string[8..9]: pi => 5번째

[3]: string[3..4]: si => 6번째

[6]: string[6..7]: si => 6번째

[2]: string[2..3]: ss => 7번째

[5]: string[5..6]: ss => 7번째

이제 표에서 g[index]가 무엇을 구하는 것인지 확실히 캐치했을 것이다.

그럼 이걸 어떻게 구할까? 보통 suffix array를 처음 공부하는 사람들은 여기서 막힌 사람들이 많다.

" 여기서 3길이 단위를 구하지 않고 어떻게 4길이 단위를 바로 구할 수 있다는 것일까? "

일단 어떻게 구하는지는 차차 설명하고 4길이 단위로 그룹번호를 매겨보겠다.

index	0	1	2	3	4	5	6	7	8	9
string[index]	m	i	s	s	i	s	s	i	p	i
g[index]	4	3	9	7	3	8	6	2	5	1

결과적으로 살펴보면 2번째 index에서 시작하는 issi와 4번째 index에서 시작하는 issi만 빼고 모두 그룹번호가 다르게 매겨졌다.

이제 다시 2개 길이 단위로 그룹번호를 지정했던 테이블을 살펴보자.

알아보기 쉽게 아래와 같이 테이블을 좀 더 상세히 그려보았다.

g[index]

2개 길이 단위에서 구분짓지 못했던 g[2]와 g[5]를 살펴보자.

위에서 g[2]와 g[5]값은 7이다.

g[2]==g[5]이므로 4개 길이 단위에서 그룹번호를 결정짓기 위해서는 아래 표의 빨간 부분을 비교해보면 된다.

g[index]

그런데 빨간 부분을 비교한다고 string[4]와 string[7]을 비교한 다음 string[5]와 string[8]을 비교하는 것일까?

아니다.

우리는 이미 2개 길이 단위의 g(그룹)값을 구하면서 string[4..5]와 string[7..8]에 해당하는 그룹번호를 알고 있다. (위의 테이블에서 보라색 부분이 바로 그 부분이다.)

즉, t개 길이 단위에서 g값이 결정되어 있을때 g[x]==g[y]이면 => g[x+t]와 g[y+t]를 비교하면 되는 것이다.

그러므로 2개 길이 단위에서 4개길이 단위를 만드는데, 최대 비교회수는 2번이다.

더 간단히 얘기하자면, (g[x],g[x+t])와 (g[y],g[y+t])를 pair<int,int>로 만들어 놓고 정렬하면 된다는 것이다.

그럼 같은 방식으로 [4개 단위에 대한 그룹번호]를 가지고 있다면 [8개 단위의 새로운 그룹번호]를 만들때에도 각각 최대 2번까지만 비교하게 된다.

O(NlgNlgN)방식은 이게 전부다.

이것을 코드로 옮겨보면 다음과 같다.

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
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
//sfx: suffix array
//g: group number
//ng: new group number
vector<int> sfx,g,ng;
vector<int> getsfx(string &s) {
    int n = s.size();
    sfx.resize(n); g.resize(n+1); ng.resize(n+1);
    for(int i=0; i<n; i++) sfx[i]=i, g[i]=s[i];
 
    g[n]=-1;
    for(int t=1; t<n; t<<=1) {
        auto cmp = [&](int i, int j) {
            if(g[i]==g[j]) return g[i+t]<g[j+t];
            else return g[i]<g[j];
        };
        sort(sfx.begin(), sfx.end(), cmp);
        ng[sfx[0]]=0;
        ng[n]=-1;
        for(int i=1; i<n; i++) {
            if(cmp(sfx[i-1],sfx[i])) ng[sfx[i]]=ng[sfx[i-1]]+1;
            else ng[sfx[i]]=ng[sfx[i-1]];
        }
        g=ng;
    }
    return sfx;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    string s; cin >> s;
    vector<int> sfx = getsfx(s);
    for(int i=0; i<sfx.size(); i++) {
        printf("%d ", sfx[i]);
    }
    return 0;
}
Colored by Color Scripter
cs

이전까지 한 설명을 모두 이해했다면, 코드도 이해하는데 어려움이 없을 것이다.

약간 헷갈리는 부분이 있을 수도 있는데,

그룹번호에 접근하는 순서가 0번부터 n-1번까지 순서대로 접근하는 것이 아니라

sfx[0]번부터 sfx[n-1]번 순서로 접근한다는 것이다.

이는 당연한데, 그룹번호가 1번인것들끼리 먼저 비교를 해야하지 않겠는가?!

한가지 좀 더 특이한 부분은 g배열을 n까지만 잡았다는 것이다. g[n+1]에 접근하는 일이 없는 것일까?

mississipi를 종이에 적고 조금만 생각해보면 그런 일은 발생하지 않는 것을 알 수 있다.

시간복잡도는 위의 코드에서 t에 관한 반복문이 1,2,4,8,16,... 형태로 진행되기 때문에 lgN이고,

각 루프마다 NlgN의 sorting을 수행하므로 O(NlgNlgN)이 된다.

이제 O(NlgN) 방법을 알아보자.

이미 눈치챘겠지만, sorting을 O(NlgN)이 아닌 O(N)에 수행하게 되면 시간복잡도는 O(NlgN)이 된다.

그럼 정렬하는 방법을 Counting Sort로 바꿔보자.

코드는 다음과 같다.

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
46
47
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
vector<int> g,ng,sfx,cnt,orderToIdx;
vector<int> getsfx(string &s) {
    int n=s.size();
    int lim = max(257,n+1);
    g.resize(n+1); ng.resize(n+1); sfx.resize(n); orderToIdx.resize(n+1);
    for(int i=0; i<n; i++) sfx[i]=i, g[i]=s[i];
    for(int t=1; t<n; t<<=1) {
        cnt.clear(); cnt.resize(lim,0);
        for(int i=0; i<n; i++) cnt[g[min(i+t,n)]]++;
        for(int i=1; i<lim; i++) cnt[i]+=cnt[i-1];
        for(int idx=n-1; idx>=0; idx--) orderToIdx[--cnt[g[min(idx+t,n)]]]=idx;
        //orderToIdx[x]=idx; => pair에서 second기준으로 정렬했을 때, second기준으로 x번째에 해당하는 index는 idx라는 뜻이다.
 
        cnt.clear(); cnt.resize(lim,0);
        for(int i=0; i<n; i++) cnt[g[i]]++;
        for(int i=1; i<lim; i++) cnt[i]+=cnt[i-1];
        for(int i=n-1; i>=0; i--) sfx[--cnt[g[orderToIdx[i]]]]=orderToIdx[i];
        //sfx[x]=idx; => pair에서 second기준으로 정렬후 first기준으로 다시 stable sort를 했을 때, 순서로 x번째에 해당하는 인덱스는 idx라는 뜻이다.
 
        auto cmp = [&](int i, int j) {
            if(g[i]==g[j]) return g[i+t]<g[j+t];
            else return g[i]<g[j];
        };
        ng[sfx[0]]=1;
        for(int i=1; i<n; i++) {
            if(cmp(sfx[i-1],sfx[i])) ng[sfx[i]]=ng[sfx[i-1]]+1;
            else ng[sfx[i]]=ng[sfx[i-1]];
        }
        g=ng;
    }
    return sfx;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    string s; cin >> s;
    vector<int> sfx = getsfx(s);
    for(int i=0; i<sfx.size(); i++) {
        printf("%d ", sfx[i]);
    }
    return 0;
}
Colored by Color Scripter
cs

보면 알겠지만, 알고리즘 공부가 부족하면 "쭤게 뭐얍!" 과 같은 상황이 발생한다.

15번째 줄부터 23번째 줄 까지가 STL sort를 사용했던 부분을 counting sort로 변경한 부분이다.

필자도 처음 suffix array를 코딩하기 전까지는 counting sort는 당연히 할줄 안다고 생각했는데, 정말 무지했다는 것을 깨달았다.

아마도 이 글을 읽는 분들은 쉽게 카운팅소트 정도야 가볍게 지나가셨을거라 생각하지만,

혹시 모를 나와 같은 극소수의 분들을 위해 조금 더 적어보겠다.

LINK : Counting Sort하는 방법 (http://plzrun.tistory.com/entry/Counting-Sort-Radix-Sort)

pair값 sorting을 counting sort로 구현하는 것이니까

second에 해당하는 g[i+t]부분을 먼저 정렬한다.

정렬하고 났을때 orderToIdx[]배열에 다음과 같이 저장하면 된다.

orderToIdx[x] = idx; => g[idx+t]를 기준으로 정렬했을 때 x번째 순서에 해당하는 인덱스 값이 idx이다.

그렇다면 second기준(g[idx+t])으로 먼저오는 인덱스 값부터 first(g[idx])를 비교해주면~! 똭~!!!

Suffix Array를 어디에 활용하는지는 다음에 설명해 보겠다. (ㅈㅅㅈㅅ)

이 글 무려 7시간동안 작성함 ㅠㅠ,, 다음에 시간날 때 마저 써야겠다.

LCP관련글은 아래에서 확인할 수 있다.

LCP: $\small O(N)$ → 약간 설명이 있는 내가 올린 포스팅: http://plzrun.tistory.com/entry/문자열-처리-알고리즘-LCP

저작자표시 비영리 변경금지

'Algorithm > String' 카테고리의 다른 글

Rabin-Karp Fingerprinting 이란? (0)	2017.01.05
Suffix Array & LCP (C++11 Code Only) (0)	2016.11.20
문자열 처리 알고리즘 - LCP (4)	2016.11.20
문자열 처리 알고리즘 - Suffix Array (0)	2016.11.20
문자열 처리 알고리즘 - KMP (2)	2016.11.20

plzrun's algorithm