접미사 배열(Suffix Array)

Suffix Array란, 문자열 S가 있을 때 그 접미사들을 정렬해 놓은 배열이다. 예를 들어, 문자열 S=banana의 접미사는 아래와 같이 총 6개가 있다.

Suffix	i
banana	1
anana	2
nana	3
ana	4
na	5
a	6

이를 Suffix 순으로 정렬하면 아래와 같다.

Suffix	i
a	6
ana	4
anana	2
banana	1
na	5
nana	3

정렬된 i의 배열 [6,4,2,1,5,3]을 S의 Suffix Array라고 한다.

(출처 :: https://www.acmicpc.net/problem/9248)

Suffix Array는 위와 같이 정의되고 Suffix Array를 구하는 방법은 다음과 같다.

단순히 접미사를 구하고, 정렬을 하는 방법은 이라는 시간 복잡도가 걸린다.

(단어 비교 시  정렬 시 )

따라서 값이 커진다면 Suffix Array를 해결하기에는 매우 불리한 알고리즘이다.

이를 해결하기 위해 현재 O(n)에 동작하는 알고리즘이 존재하긴 하지만, 

이 알고리즘은 너무 복잡하기에 PS(Problem Solving)에서는 이용하지 않는다.

그래서 이번에는 에 동작하는 맨버-마이어스 알고리즘(Manber-Myers Algorithm)에 대해 알아보려 한다.

맨버-마이어스 알고리즘의 기본 동작 원리는 다음과 같다.

첫 1, 2, 4, 8 ... 2^n 글자를 기준으로 정렬하는 방식이다.

이렇게 logn번의 정렬을 하고 나면 원하는 접미사 배열을 얻을 수 있게 된다.

예를 들어 위의 banana에 대해 알아보자.

정렬되지 않은 Suffix가 이렇게 있다.

이때 맨버-마이어스 알고리즘에 의해 정렬을 하게 된다면 우선 첫 한 글자를 기준으로 정렬을 한다.

이 후, 첫 두 글자를 기준으로 정렬을 한다.

이 후, 첫 네 글자를 기준으로 정렬을 한다.

이 후로는 문자열의 길이가 banana = 6이므로 첫 여덟 글자 기준은 정렬할 필요가 없다.

시간 복잡도

이렇게 정렬을 하게 되면 번의 정렬을 하고 매번 정렬을 하는데 이므로 

결국의 시간이 걸리게 된다.

소스 코드를 통해 맨버-마이어스 알고리즘을 다시 한번 파악해보자.

소스 코드

#include <cstdio>
#include <algorithm>
#include <cstring>
 
#define MAX_N 600000
using namespace std;
 
/*
str :: 문자열이 들어갈 배열
t :: 단어의 위치를 보는 변수
n :: str의 길이
g :: 그룹
tg :: 팀 그룹
SA :: Suffix Array
*/
 
char str[MAX_N];
int t, n, g[MAX_N], tg[MAX_N], SA[MAX_N];
 
bool cmp(int x, int y)
{
    // 그룹 번호가 같으면
    if (g[x] == g[y])
        return g[x + t] < g[y + t];
 
    // 그룹 번호가 다르면
    return g[x] < g[y];
}
 
void getSA(const char* str)
{
    t = 1;
    n = (int)strlen(str);    //글자의 수 배정
 
    //첫 글자에 의한 그룹을 정해주는 전처리
    for (int i = 0; i < n; i++)
    {
        SA[i] = i;
        g[i] = str[i] - 'a';
    }
 
    //1,2,4,8... 씩 단어의 길이보다 작은 경우를 탐색
    while (t <= n)
    {
        g[n] = -1;
        sort(SA, SA + n, cmp);    //그룹에 의한 정렬
        tg[SA[0]] = 0;    //다음 그룹을 할당하기 위하여 tempgroup의 첫번째 번호 배정
 
        //다음 그룹 배정 
        for (int i = 1; i < n; i++)
        {
            //그룹이 다를 경우 다음 그룹 번호 할당
            if (cmp(SA[i - 1], SA[i]))
                tg[SA[i]] = tg[SA[i - 1]] + 1;
 
            //그룹이 같을 경우 같은 그룹 번호 할당
            else
                tg[SA[i]] = tg[SA[i - 1]];
        }
 
        //새로운 그룹 할당
        for (int i = 0; i < n; i++)
            g[i] = tg[i];
 
        t <<= 1; // t *= 2;
    }
}
 
int main()
{
    scanf("%s", &str);
    getSA(str);
 
    printf("\n[Suffix Array]\n");
    for (int i = 0; i < n; i++)
        printf("%s\n", str + SA[i]);
 
    printf("\n[Suffix Array Order]\n");
    for (int i = 0; i < n; i++)
        printf("%d ", SA[i] + 1);
 
    printf("\n\n");
 
 
    return 0;
}

소스코드 출처 :: http://jason9319.tistory.com/141

소스 코드 설명

    scanf("%s", &str);

    getSA(str);

str을 통해 입력을 받고 getSA 함수로 str 인자를 보내준다.

void getSA(const char* str)

{

    t = 1;

    n = (int)strlen(str);    //글자의 수 배정

t = 1로 시작하고, n은 str의 길이를 받아둔다.

    //첫 글자에 의한 그룹을 정해주는 전처리

    for (int i = 0; i < n; i++)

    {

        SA[i] = i;

        g[i] = str[i] - 'a';

    }

그리고 SA(Suffix Array)에는 0번부터 차례로 넣어주고

g[i]는 첫 한 글자를 기준으로 같은 그룹끼리 번호를 넣어준다.

(즉, banana에서 anana, ana, a는 0번, banana는 1번, nana, na는 13번이 된다.)

결국 첫 한 글자를 기준으로 할 때 

g[0] :: banana :: 1

g[1] :: anana :: 0

g[2] :: nana :: 13

g[3] :: ana :: 0

g[4] :: na :: 13

g[5] :: a :: 0

이 된다.

    //1,2,4,8... 씩 단어의 길이보다 작은 경우를 탐색

    while (t <= n)

    {

반복문은 t가 n보다 작거나 같을 때 까지 반복하면 된다.

        sort(SA, SA + n, cmp);    //그룹에 의한 정렬

반복문에 들어서서

sort를 확인해보면 cmp라는 정렬 조건이 있다.

bool cmp(int x, int y)

{

    // 그룹 번호가 같으면

    if (g[x] == g[y])

        return g[x + t] < g[y + t];

 

    // 그룹 번호가 다르면

    return g[x] < g[y];

}

이 cmp는 그룹 번호에 따라 SA를 정렬 하게 되어있다.

이렇게 처음 정렬을 끝내고 나면

SA[] = {0,1,2,3,4,5}였던 것이

SA[] = {5,1,3,0,2,4}로 바뀌게 된다.

즉, a / anana / ana / banana / nana / na순서로 바뀌었다는 의미이다.

       tg[SA[0]] = 0;    //다음 그룹을 할당하기 위하여 tempgroup의 첫번째 번호 배정 

이후 팀그룹을 의미하는 tg의 SA[0]는 0으로 설정한다.

즉 tg[SA[0]] -> tg[5] = 0이다.

        //다음 그룹 배정 

        for (int i = 1; i < n; i++)

        {

            //그룹이 다를 경우 다음 그룹 번호 할당

            if (cmp(SA[i - 1], SA[i]))

                tg[SA[i]] = tg[SA[i - 1]] + 1;

 

            //그룹이 같을 경우 같은 그룹 번호 할당

            else

                tg[SA[i]] = tg[SA[i - 1]];

        }

다음 for문에서는 cmp 함수를 다시 이용하여 SA[i-1]과 SA[i]의 그룹 번호를 비교하여 정렬한다.

SA는 현재 SA = {5,1,3,0,2,4}이고 g는 현재 g[] = {1,0,13,0,13,0}이므로 cmp에서 하나씩 보자면

bool cmp(int x, int y)

{

    // 그룹 번호가 같으면

    if (g[x] == g[y])

        return g[x + t] < g[y + t];

 

    // 그룹 번호가 다르면

    return g[x] < g[y];

}

x = SA[0], y = SA[1]이니

g[5] == g[1] ?인지 묻고있는 것과 같다.

g[5] = 0 g[1] = 0이니 g[6]과 g[2]에의 참 거짓을 판별 후 리턴해야한다.

g[6] = -1(처음에 g[n] = -1)이고 g[2] = 13이니 true를 반환하고 

tg[1] = tg[5] + 1을 해준다.

이렇게 for문을 마무리 하면 tg는 다음과 같게 나타난다.

tg[] = {2,1,3,1,3,0}

이렇게 tg를 만들어가는 것은, 처음부터 t번째 글자 기준으로 그룹이 될 대상을 만들어준다는 의미한다. 

        //새로운 그룹 할당

        for (int i = 0; i < n; i++)

            g[i] = tg[i];

그렇게 만들어진 tg를 g에 다시 넣어준다.

        t <<= 1; // t *= 2;

마지막으로 t에 2를 곱하여 준다.(첫 한 글자, 첫 두 글자, 첫 네 글자, .. 기준)

코드 추적

banana에 대한 상세한 추적 결과는 아래와 같다.