접미사 배열 - 맨버/마이어스의 알고리즘

다양한 문자열 문제를 해결하기 위해서는 접미사 배열(suffix array) 자료구조를 이해해야한다.

접미사 배열은 어떤 문자열 S의 모든 접미사를 사전순으로 정렬해 둔 것이다. 이 말 그래도 모든 접미사들을 문자열 배열에 저장하면 문자열 길이의 제곱에 비례하는 메모리가 필요하기 때문에, 대개 접미사 배열은 각 접미사의 시작 위치를 담는 정수 배열로 구현된다.

 

예를 들면 아래 표는 문자열 "alohomora"의 접미사 배열 A[]와 각 위치에서 시작하는 접미사들을 보여준다.

i	A[i]	S[A[i] ..]
0	8	a
1	0	a l o h o m o r a
2	3	h o m o r a
3	1	l o h o m o r a
4	5	m o r a
5	2	o h o m o r a
6	4	o m o r a
7	6	o r a
8	7	r a

 

접미사 배열을 이용해 할 수 있는 대표적인 일이 문자열 검색이다. 접미사 배열을 이용한 문자열 검색은 전체 문자열 H가 찾고자 하는 문자열 N을 포함한다면 항상 N은 H의 어떤 접미사의 접두사라는 점을 이용한다.

 

이 속성을 이용하면 H의 접미사 배열을 이진 탐색해서 각 문자열이 출현하는 위치를 찾을 수 있다. 접미사 배열의 길이는 항상 |H|이므로 이진 탐색의 내부는 O(lg|H|)이 된다. 

 

 

---

접미사 배열을 만드는 맨버-마이어스의 알고리즘

해당 알고리즘은 접미사들의 목록을 여러 번 정렬하는데, 매번 그 기준을 바꾼다. 처음에는 접미사의 첫 한 글자만을 기준으로 정렬하고, 다음에는 접미사의 첫 두 글자를 기준으로 정렬하고, 그 다음에는 접미사의 첫 네 글자를 기준으로 정렬한다. 이렇게 lgn번의 정렬을 하고 나면 우리가 원하는 접미사 배열을 얻을 수 있다. 

 

 

[문자열 "mississipi"의 접미사들을 첫 한 글자 기준으로 정렬했을 때]

첫 한 글자 기준

ississipi issipi ipi i

mississipi

pi

ssissipi sissipi ssipi sipi

 

첫 글자를 기준으로 접미사들을 정렬한 결과를 위처럼 가지고 있다고 하자. 각 접미사들을 첫 글자가 같은 것들끼리 그룹으로 묶고, 각 그룹마다 0부터 시작하는 번호를 매긴다. 위 표로 보면 i로 시작하는 접미사들은 0번 그룹, m으로 시작하는 접미사들은 1번 그룹, p로 시작하는 접미사들은 2번 그룹, s로 시작하는 접미사들은 3번 그룹으로 묶이게 된다. 이제 다음과 같은 배열 group[]을 만들어준다.

 

group[i] = S[i┈]가 속한 그룹의 번호

 

첫 t글자를 기준으로 만든 group[]이 있으면 두 접미사 S[i┈], S[j┈] 중 첫 t글자를 기준으로 어느 쪽이 더 앞에 오는지 쉽게 알 수 있다. group[i]와 group[j] 중 어느 쪽이 더 작은지를 확인하면 된다. 

 

그런데 이것만 있으면 S[i┈]와 S[j┈] 중 첫 2t글자를 기준으로 어느 쪽이 사전에서 앞에 오는지도 상수 시간에 판단할 수 있다.

S[i┈]와 S[j┈]가 주어질 때, 우선 첫 t글자를 비교한다. 만약 이들이 서로 다르다면 나머지는 볼 것도 없이 어느 쪽이 앞에 오는지 결정가능하다. 만약 두 접미사가 같은 그룹에 속한다면 S[i+t┈]와 S[j+t┈]의 첫 t글자를 서로 비교하면 된다.

 

아래 코드는 이와 같은 비교 방식을 구현한 비교자 코드이다. 해당 코드를 만들고 나면 이제 첫 2t글자를 기준으로 해서 접미사들을 O(nlgn) 시간에 정렬 가능하다. 그러고 나면 다시 이들을 순회하면서 O(n) 시간에 그룹을 지을 수 있다.

// 각 접미사들의 첫 t글자를 기준으로 한 그룹 번호가 주어질 때,
// 주어진 두 접미사를 첫 2*t글자를 기준으로 비교한다.
// group[]은 길이가 0인 접미사도 포함한다.
struct Comparator{
    const vector<int> &group;
    int t;
    Comparator(const vector<int>& _group, int _t): group(_group), t(_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┈]의 첫 t글자 비교
        return group[a+t] < group[b+t];
    }
};

 

코드를 확인하면 group[a+t]과 group[b+t]가 배열 범위 밖의 값이 아닌지 확인하지 않는다. 어떻게 가능한 것일까?

이 두 값을 참조하는 경우는 두 접미사의 첫 t글자가 같을 때 뿐인데, 그러기 위해서는 두 접미사의 길이는 모두 t이상이어야한다. 따라서 이 경우 a+t와 b+t는 최대 N이 된다. 따라서 group[n]을 아주 작은 값으로 두면 범위 확인 없이 모든 경우를 처리할 수 있다.

 

아래는 전체 알고리즘의 구현 코드이다.

// s의 접미사 배열 계산
vector<int> getSuffixArray(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;
    
    // 결과적으로 접미사 배열이 될 반환 값. 이 배열을 lg(n)번 정렬한다.
    vector<int> perm(n);
    for(int i=0;i<n;++i) perm[i] = i;
    
    while(t < n){
    	// group[]은 첫 t글자를 기준으로 계산해뒀다.
        // 첫 2t글자를 기준으로 perm을 다시 정렬한다.
        Comparator compareUsing2T(group, t);
        sort(perm.begin(), perm.end(), compareUsing2T);
        
        // 2t글자가 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]];
        }
        group = newGroup;
    }
    return perm;
}

t글자를 기준으로 각 접미사를 그룹에 배정한 뒤, 이 정보를 이용해 2t글자를 기준으로 정렬하는 과정을 반복하는 것을 볼 수 있다. 

 

• t=1일 때는 실제로 직접 정렬을 하는 것이 아니라 해당 접미사의 첫 글자를 그룹 번호로 배정한다. 그룹 번호가 0부터 시작하는 정수가 아니게 되지만, 어차피 Comparator는 그룹 번호의 대소관계만을 이용하므로 상관없다.
• group[]의 크기는 n+1이며, 길이 0인 접미사를 나타내는 group[n]의 값은 항상 -1이다. 길이가 0인 접미사는 접미사 배열의 반환 값에 포함되지 않지만, 앞에서 설명한 것과 같이 Comparator가 group[n]에 접근하기 때문에 필요하다. 어차피 길이가 0인 접미사는 몇 글자를 기준으로 정렬하건 항상 가장 앞에 오기 때문에, group[n]은 -1로 고정해 둔 채 변경하지 않아도 된다.

 

while문 내부의 시간 복잡도는 O(nlgn)의 시간이 걸리는 정렬이 지배하므로, 전체 시간 복잡도는 O(nlg^2n)이 된다.

 

 

참고 : 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2 - 문자열