티스토리 뷰

알고리즘 이론

Suffix Array, LCP Array

museop 2017. 2. 22. 22:48

Suffix Array


접미사 배열(suffix array)는 어떤 문자열 S의 모든 접미사를 사전순으로 정렬해둔 것으로, 보통 각 접미사의 시작 위치를 저장하는 정수 배열로 구현된다. 길이가 \(n\)인 문자열의 접미사 배열을 만드는 가장 빠른 알고리즘은 \(O(N)\)만에 접미사 배열을 만든다고 한다. 하지만 프로그래밍 대회에서는 이 복잡한 알고리즘을 직접 구현하여 사용하기에는 어려워 보통 그 대안으로 적당히 구현하기 쉽고, 적당히 빠른 알고리즘을 대신 사용한다.


접미사 배열을 만드는 \(O(N{log_2}^2N)\) 알고리즘은 각 접미사를 첫 한 글자로 정렬하고, 그 다음에 두 글자, 네 글자.. 로 \(log_2N\) 번 정렬하는 것이다. 각 접미사들이 서로 완전히 다른 문자열들이 아니라 두 접미사중 하나가 다른 하나를 포함하고 있기 때문에 이전 정렬에서 얻은 정보를 이용해서 두 접미사의 대소 비교를 \(O(1)\)에 수행한다.


구현

접미사 배열을 만드는 \(O(N{log_2}^2N)\) 알고리즘은 다음과 같이 구현할 수 있다.
?
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
48
49
50
51
52
53
// 각 접미사들의 첫 t글자를 기준으로 한 group 번호가 주어질 때,
// 주어진 두 접미사를 첫 2*t 글자를 기준으로 비교한다.
// (group 번호가 낮을 수록 t 글자를 기준으로 앞에 있다. t 글자가 같을 경우 group 번호는 같다.)
struct Comparator {
    const vector<int>& group;
    const int t;
 
    Comparator(const vector<int>& _group, const int _t)
        : group(_group), t(_t) {
    }
 
    bool operator() (const int l, const int r) {
        if (group[l] != group[r])
            return group[l] < group[r];
        return group[l + t] < group[r + t];
    }
};
 
// str의 접미사 배열을 생성한다.
vector<int> getSuffixArray(const string& str) {
    int n = str.length();
    vector<int> ret(n);
 
    vector<int> group(n + 1);
    for (int i = 0; i < n; i++) {
        ret[i] = i;
        group[i] = str[i];
    }
    group[n] = -1;
 
    // 각 접미사를 첫 1, 2, 4, 8, ... 글자를 기준으로 정렬해나간다.
    int t = 1;
    while (t < n) {
        Comparator comparator(group, t);
        sort(ret.begin(), ret.end(), comparator);
 
        t *= 2;
        if (t >= n) break;
 
        vector<int> newGroup(n + 1);
        newGroup[n] = -1;
        newGroup[ret[0]] = 0;
        for (int i = 1; i < n; i++) {
            if (comparator(ret[i - 1], ret[i]))
                newGroup[ret[i]] = newGroup[ret[i - 1]] + 1;
            else
                newGroup[ret[i]] = newGroup[ret[i - 1]];
        }
        swap(group, newGroup);
    }
 
    return ret;
}


위의 알고리즘에서는 정렬 시에 보통의 \(O(Nlog_2N)\) 알고리즘을 사용하지만, 선형 시간복잡도를 가지는 계수 정렬(Counting Sort)를 이용하면, 아래와 같이 접미사 배열을 만드는 총 시간복잡도를 \(O(Nlog_2N)\)로 줄일 수 있다.  


?
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// 첫 k 글자를 기준으로 매겨진 group 번호를 이용하여 접미사 배열을 계수 정렬한다.
void countingSort(int k, vector<int>& perm, vector<int>& group) {
    int n = perm.size();
 
    // 계수 정렬시 사용하는 bucket의 범위
    // 첫 group 번호는 문자의 아스키 코드를 이용하므로 char의 최댓값을 담을 수 있어야 하고,
    // 그 이후에는 0번부터 최대 n-1까지 매겨질 수 있으므로 이에 맞게 range를 잡는다.
    int range = max(n, (int)numeric_limits<char>::max());
 
    vector<int> cnt(range + 1, 0);
    for (int i = 0; i < n; i++) {
        if (i + k < n)
            cnt[group[i + k]]++;
        else
            cnt[0]++;
    }
 
    for (int i = 1; i <= range; i++) {
        cnt[i] += cnt[i - 1];
    }
 
    vector<int> newPerm(n);
    for (int i = n - 1; i >= 0; i--) {
        if (perm[i] + k < n)
            newPerm[--cnt[group[perm[i] + k]]] = perm[i];
        else
            newPerm[--cnt[0]] = perm[i];
    }
    swap(perm, newPerm);
}
 
// 문자열 s의 접미사 배열을 반환한다.
vector<int> getSuffixArray(const string& s) {
    int n = s.size();
 
    // 접미사 배열, 각 접미사의 시작 위치를 저장하는 순열로 볼 수 있다.
    vector<int> perm(n);
    for (int i = 0; i < n; i++) {
        perm[i] = i;
    }
 
    // 각 접미사들의 첫 k 글자를 기준으로 매겨진 group 번호
    // 첫 k 글자가 사전상 앞에 있을 수록 상대적으로 낮은 번호를 부여한다.
    vector<int> group(n + 1);
    for (int i = 0; i < n; i++) {
        group[i] = s[i];
    }
 
    // 각 접미사를 첫 2, 4, 8, ... 글자를 기준으로 O(lg n)번 정렬한다.
    for (int k = 1; k < n; k *= 2) {
        countingSort(k, perm, group); // 첫 [k ~ 2*k) 글자를 기준으로 정렬
        countingSort(0, perm, group); // 첫 [0 ~ k) 글자를 기준으로 정렬
 
        // group 번호를 갱신한다.
        vector<int> newGroup(n + 1); // 새 group 번호 (임시 배열)
        newGroup[perm[0]] = 0;
        for (int i = 1; i < n; i++) {
            if (group[perm[i]] == group[perm[i - 1]] && group[perm[i] + k] == group[perm[i - 1] + k])
                newGroup[perm[i]] = newGroup[perm[i - 1]];
            else
                newGroup[perm[i]] = newGroup[perm[i - 1]] + 1;
        }
 
        swap(group, newGroup);
 
        if (group[perm[n - 1]] == n - 1) break; // 최적화
    }
 
    return perm;
}


Longest Common Prefix Array


접미사 배열과 함께 자주 사용되는 것이 있는데 바로 LCP 배열이다. Longest Common Prefix, 말 그대로 가장 긴 공통 접두사를 의미하는데, 여기서 말하는 LCP 배열은 (사전순으로 정렬되어 있는) 접미사 배열에서 이전 접미사와의 최장 공통 접두사의 길이를 저장한다. 문자열, 그 문자열의 접미사 배열, 그리고 LCP 배열의 관계는 아래 표를 보면 이해하기가 쉽다.



 i

suffixArray[ i ] 

suffix 

LCP[ i ] 

 0

 5

 a

 

 1

 3

 ana

 1

 2

 1

 anana

 3

 3

 0

 banana

 0

 4

 4

 na

 0

 5

 2

 nana

 2


LCP 배열은 접미사 배열에서 사전상으로 인접한 두 접미사의 최장 공통 접두사의 길이를 하나 하나 세면 되지만, 이 방식은 \(O(N^2)\)의 시간이 소요되는 방식이다. 이 LCP 배열을 계산하는 보다 효율적인 \(O(N)\) 알고리즘이 존재하는데 그 핵심 아이디어는 접미사 배열을 계산할 때와 마찬가지로 한 접미사는 다른 접미사의 접미사라는 점을 이용하여 중복된 계산을 줄이는 것이다.



 i

suffixArray[ i ] 

suffix 

LCP[ i ] 

 0

 5

 a

 

 1

 3

 ana

 1

 2

 1

 anana

 3

 3

 0

 banana

 0

 4

 4

 na

 0

 5

 2

 nana

 2



위의 접미사 배열에서 인접한 접미사 "ana"와 "anana"의 LCP는 3이라는 것을 계산했다고 하자. 그 후에 "na", "nana"의 LCP를 계산하려고 할 때, 한 가지 사실을 알 수 있다. 이미 "ana"와 "anana"의 LCP는 3이라고 계산해두었기 때문에 앞의 a가 없는 "na"와 "nana"의 LCP는 최소 2라는 사실이다. (보다 자세한 내용은 여기를 참고하면 될 것 같다.)


즉, S[i..], 그리고 S[i..]와 사전상으로 인접한 접미사(접미사 배열상 바로 이전 접미사)와의 LCP를 \(m\)이라고 하면, S[i+1..], S[i+1..]와 사전상으로 인접한 접미사의 LCP는 최소 \(m-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
25
26
27
// 문자열 s와 s의 접미사 배열이 주어졌을때, LCP 배열을 생성한다.
vector<int> getLCPArray(const string& s, vector<int>& suffixArray) {
    int n = s.length();
 
    vector<int> lcp(n);
 
    // rank[i]: s[i..]가 사전상 몇 번째 접미사인지를 나타낸다.
    vector<int> rank(n);
    for (int i = 0; i < n; i++)
        rank[suffixArray[i]] = i;
 
    int matched = 0;
    for (int i = 0; i < n; i++) {
        int k = rank[i];
        if (k) {
            int j = suffixArray[k - 1];
            while (s[j + matched] == s[i + matched])
                ++matched;
 
            lcp[k] = matched;
 
            if (matched)
                --matched;
        }
    }
    return lcp;
}



예제


참고 자료


저작자표시

'알고리즘 이론' 카테고리의 다른 글

Modular Arithmetic  (0) 2017.03.18
탐색 (Searching)  (0) 2017.03.06
Counting Sort, Radix Sort  (0) 2017.02.23
트리의 지름 (Diameter of Tree)  (0) 2017.02.20
KMP Pattern Searching  (0) 2017.02.20
공유하기 링크
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/04   »
일 월 화 수 목 금 토
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
글 보관함