[자료구조] Suffix Array(접미사 배열)

컴퓨터 과학에서 접미사 배열(Suffix Array)란 어떤 문자열의 접미사를 사전식 순서대로 나열한 배열을 말한다.

 

S = S[0]S[1]...S[n-1] 이라는 문자열이 있다고 하자.

이때 

S[i,j] 는 i번째 문자부터 j번째 문자 까지 S의 부분 문자열이라고 하자.

문자열 S에 대한 접미사 배열 A는 S의 접미사들을 사전식 순서로 정렬 했을 때 접미사의 시작 위치를 저장한 정수 배열이다.

즉 A[i] 에 저장 된 내용은 사전순으로 i 번째인 S의 접미사의 시작 위치이다.

다시 말하면

문자열 S의 길이를 n이라고 할 때 , 0<i<n 인 i 에 대해 사전 순으로

S[A[i-1],n] < s[A[i],n] 이다.

 

예를 살펴 보자.

다음과 같이 문자열 S="banana" 가 있다.

i	0	1	2	3	4	5	6
S[i]	b	a	n	a	n	a	$

문자열의 끝은 사전순으로 어떠한 문자보다 앞서기 때문에 $ 라는 특수 문자로 표시했다.

이때 문자열 S의 접미사들은 다음과 같이 나눌 수 있다.

접미사	i
banana$	1
anana$	2
nana$	3
ana$	4
na$	5
a$	6
$	7

 

이러한 접미사들을 정렬하면 다음과 같다.

접미사	i
$	7
a$	6
ana$	4
anana$	2
banana$	1
na$	5
nana$	3

이 때 접미사 배열 A는 위와 같이 정렬된 접미사의 시작 위치를 저장한 배열이다. 따라서 A 배열은 다음과 같다.

i	0	1	2	3	4	5	6
A[i]	7	6	4	2	1	5	3

예를 들어 A[2] 에 4라는 값이 저장되어 있는데 이는 S의 접미사를 사전 순으로 정렬 했을 때 세번째에 위치하는 접미사가 시작 인덱스가 4인 ana$ 라는 의미이다.

 

이러한 접미사 배열을 구현하는 알고리즘은 다음과 같다.

 

1. 일반적인 알고리즘은 n개의 접미사 배열을 만든 후 사전순으로 정렬하여 나열하는 방법이 있다.

이 알고리즘은 비교하는 횟수 O(_nlg_n) 과 사전순서를 판단하는데 필요한 비교횟수 O(n)이므로 총 시간 복잡도는 O(_n²lg_n) 이 된다.

2. Manber-Myers 알고리즘

Manber-Myers 알고리즘은 정렬할 때 랭크 라는 개념과 기수 정렬을 사용하여 시간 복잡도를 줄인 알고리즘이다. 이 알고리즘은 접미사 배열을 구하는 다양한 알고리즘 가운데 프로그래밍 대회에서 자주 사용되는데 시간복잡도가 더 작은 알고리즘은 짧은 시간 안에 구현하기 어렵기 때문이다.

알고리즘은 다음과 같다.

1) 첫글자를 기준으로 정렬한다.

2) 두번째 글자를 기준으로 정렬한다.

3) 4번째 글자를 기준으로 정렬한다.

4) 8번째 글자를 기준으로 정렬한다.

...

위와 같이 1,2,4,8 ... 과 같이 2의 거듭제곱 위치를 비교 하여 정렬해 주면 된다.

이때 각 자리의 시작 위치를 그룹 번호로 만들어서 해당 그룹 번호로 정렬을 해 주면 다음과 같이 된다.

 

 

접미사	num	group
banana0	0	98
anana	1	97
nana	2	110
ana	3	97
na	4	110
a	5	97

이것을 group 위치로 정리하는데 첫번째 자리가 같다면 두번째 자리 위치를 기준으로 정렬을 한다.

접미사	num	group
a	5	97
anana	1	97
ana	3	97
banana	0	98
nana	2	110
na	4	110

이렇게 1번째 자리로 정렬을 한 후에 2번째 자리를 이용해서 그룹 번호를 다시 만들자.

맨 처음에 나온 그룹 번호를 0으로 만들고 1번째 자리가 앞과 같으면 2번째 자리를 기준으로 크기 비교를 하여 앞과 같다면 앞과 같은 그룹 번호를 부여하고 아니면 앞에 보다 큰 그룹 번호를 부여한다.

접미사	num	group
a	5	0
anana	1	1
ana	3	1
banana	0	2
nana	2	3
na	4	3

이 그룹 번호로 다시 정렬을 하는데 그룹 번호가 같다면 +2인 그룹 번호 위치를 기준으로 정렬한다.

즉 위에서 anana 1번과 ana 3 번을 비교할때 1번 그룹과 3번 그룹의 크기가 같으므로 1 + 2의 3번 그룹과 3 + 2 의 5번 그룹의 크기로 비교를 해 준다.

이렇게 정렬을 하면 다음과 같다.

접미사	num	group
a	5	0
ana	3	1
anana	1	1
banana	0	2
na	4	3
nana	2	3

여기서 가장 마지막 그룹번호($)는 -1로 만들어서 가장 작은 값을 만들어 주면 된다.

 

 

구현 코드는 다음과 같다.

///각 접미사들의 첫 t글자를 기준으로 한 그룹 번호가 주어질때
///주어진 두 접미사를 2*t 글자를 기준으로 비교한다.
///group[]은 길이가 0인 접미사도 포함한다.
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)
    {
        ///첫 t글자가 다르면 이들을 이용하여 비교한다.
        if(group[a] != group[b]) return group[a]<group[b]; //그룹순이 작은게 작은것이다.
        ///아니라면 S[a+t]와 S[b+t] 의 글자를 비교한다.
        return group[a+t] < group[b+t];
    }
};

//s의 접미사 배열을 계산한다.
vector<int> suffix(const string &s)
{
    int n=s.size();
    ///group[i] = 접미사드을을 첫 t글자를 기준으로 정렬했을때
    ///S[i] 가 들어가는 그룹번호
    ///t=1일때는 정렬할 것 없이 s[i]의 첫글자로 그룹번호를 정해 줘도 같은 효과가 있다.
    int t=1;
    vector<int> group(n+1);
    for(int i=0;i<n;i++) group[i]=s[i];
    group[n]=-1; ///마지막을 가장 빠르게 하기 위해서 -1 값을 넣어 준다.

    ///접미사 시작 위치를 담은 배열을 만든다. 이 배열을 log(n)번 정렬한다.
    vector<int> perm(n);
    for(int i=0;i<n;i++)perm[i]=i;

    while(t<n){
        vectorPrint(group);
        vectorPrint(perm);
        ///group[]은 첫글자를 기준으로 계산해 두었다.
        ///첫 2*t글자를 기준으로 perm을 다시 정렬한다.
        Comparator compareUsing2T(group,t);
        sort(perm.begin(),perm.end(),compareUsing2T);
        vectorPrint(perm);
        ///2*t글자가 n을 넘는다면 이제 접미사 배열 환성.
        t*=2;
        if(t>=n) break;
        ///2t 글자를 기준으로 한 그룹 정보를 만든다.
        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]];
        }
        vectorPrint(newGroup);
        group = newGroup;
    }
    return perm;
}

 

 

참고)

https://ko.wikipedia.org/wiki/%EC%A0%91%EB%AF%B8%EC%82%AC_%EB%B0%B0%EC%97%B4

접미사 배열 - 위키백과, 우리 모두의 백과사전

https://blog.myungwoo.kr/57

Suffix Array와 LCP

http://www.secmem.org/blog/2021/07/18/suffix-array-and-lcp/

Suffix Array and LCP Array