[알고리즘] manber myers

manber myers알고리즘은 접미사 배열을 빠르게 정렬할 수 있는 알고리즘이라고 생각하면 된다. 여기에서 접미사는

banana가 있을 경우 banana, anana, nana, ana, na, a가 있다. 즉, manber myers알고리즘은 이러한  banana, anana, nana, ana, na, a를 사전순으로 정렬할 수 있다는 것이다.

 

이 알고리즘은 주어진 문자열이 50만 이상일 경우 사용이 된다. 보통 문자열을 정렬하기 위해서는 O(n^2* logn)의 시간이 소요 된다. 정렬하는데 O(nlogn), 문자열 비교하는데 O(n) => O(n^2 * logn)의 시간이 나오게 된다. 하지만, manber myers알고리즘을 활용한다면 O(n (logn)^2)의 시간이 소요된다. 이 시간복잡도는 정렬 O(nlogn)과 문자열 비교에서 O(logn)이 나오게 된다. 

 

자. 이제 알고리즘의 원리를 살펴보자.

우선 정렬이 되는 방식을 그림으로 설명해보겠다.

하.. 이거 진짜 어렵네..

일단 하는 방법을 알려주고 되는 원리는 나중에 설명하도록 하겠다.

 

여기에서 설명하는 용어를 정리하겠다. R은 결국에는 마지막에 사전순이라고 생각하면 된다.

아래에 나와있는 것처럼 banana가 0, anana가 1, nana가 2 ... 라고 생각해야 한다. 

다음으로 G이다. R은 G에 담겨있는 숫자에 의해 정렬이 된다. 즉, G는 그룹이라고 생각하면 된다.

TG는 다음 그룹에 담겨있어야 할 팀 그룹이다. 아래 팀그룹이라고 써져있는 곳을 확인해보면 정렬이 불가능한 것 끼리는 팀그룹으로 동일한 숫자가 부여되는 것을 알 수 있고, 비교가 가능한 ana, banana와 같은 경우 +1이 되는 것을 확인할 수 있다.

자 마지막에 나와있는 R이 답이 된다. 맨 위에서 말한 것 처럼 R[0]에 저장되어 있는 5는 a를 의미하고, 3은 ana, 1은 anana를 의미한다. 

조금만 보더라도 이해가 되지 않을 것이다. 중간에 나는 1칸, 2칸, 4칸으로 건너뛰었다. 4칸 다음에는 8칸으로 건너뛰게 된다. 이렇게 한 이유는 이렇게 해도 정렬이 되기 때문이다. 

우리는 비교를 다음과 같은 코드를 활용한다.

bool cmp(int a, int b) {
    if (G[a] == G[b]) return G[a + t] < G[b + t];
    return G[a] < G[b];
}
std::sort(R, R + len, cmp);

G에는 n번째에 해당하는 수가 몇번째 그룹에 속하는 지 표현이 된다. 즉, G의 값이 정렬이 되는 수라고 생각해야 한다. 위에서 보여준 것처럼 TG 부분에 0 1 1 2 3 4로 되어있는 부분이 있다. 0과 3을 비교하면 0이 더 작기 때문에 a가 먼저 오게 된다. 하지만, 1 과 1를 비교하기 위해서는 G[A+T]와 G[B+T]를 비교해야 한다.

이 부분을 약간 직관적으로 이해해야 해서 어렵지만, 최대한 설명을 해보겠다.

G의 n번째 배열은 가장 위에서 설정한 banana, anana, nana, ana순이라고 생각해야 한다. 그러니까 G[0] = 2가 마지막에서 두번째에 TG에 쓰여져 있는 부분이 된다. 0번째는 banana이고, banana왼쪽 TG부분에는 2가 쓰여져 있는 것을 확인할 수 있다.

그러니까 a와 b의 그룹이 같을 경우 a+t와 b+t의 그룹을 확인하여 더 작은 쪽이 더 낮은 G을 받게 된다.

여기에서의 설명을 보면 1 -> 2 -> 4 -> 8번째를 확인한다고 하였다. 그렇다면 만약 3번째 수가 다르다고 생각하면 어떻게 될까? 를 생각해야 한다. 

abaaaaab

abababbbaaab를 비교해보자.

0번째, 1번째, 2번째, 4번째는 둘 다 동일하다. 이것은 어떻게 비교가 될까?

여기에서 비교를 이런식으로 하는 것이 위험하다.

우리는 ab까지는 그룹이 동일하게 된다.

하지만, abaa와 abab를 비교할 때는 그룹이 달라지게 된다. 왜냐?

먼저 ab와 ab가 같아 그룹이 동일해지기 때문에 다음 aba"a"의 그룹과 aba"b"의 그룹을 비교하기 때문이다. 

aba"a"와 aba"b"에서의 a와 b의 그룹은 aba"a"의 a가 더 그룹이 높을 것이다. 어쩌면 현재 비교할 abababbbaaab와 abaaaaab의 그룹과 동일할 수 있다. 그렇기 때문에 abaaaaab가 더 높은 순위로 정렬이 되는 것이다.

 

이제 코드를 확인하면서 정리를 해보자.

#include <cstdio>
#include <algorithm>

char S[1001];
int R[1001], G[1001], TG[1001], len = 0, t;

bool cmp(int a, int b) {
    if (G[a] == G[b]) return G[a + t] < G[b + t];
    return G[a] < G[b];
}

int main(void) {
    scanf("%s", S);
    for (; S[len]; len++) {
        R[len] = len;
        G[len] = S[len];
    }
    G[len] = -1, TG[len] = -1;

    t = 1;
    while (t <= len) {
        std::sort(R, R + len, cmp);
        TG[R[0]] = 0;
        for (int i = 1; i < len; i++) {
            if (cmp(R[i - 1], R[i])) TG[R[i]] = TG[R[i-1]] + 1;
            else TG[R[i]] = TG[R[i - 1]];
        }

        for (int i = 0; i < len; i++) G[i] = TG[i];
        t *= 2;
    }
}

 

이 부분은 위의 그림 중에서 가장 처음 부분의 그림이다. 초반 설정을 나타낸다.

for (; S[len]; len++) {
        R[len] = len;
        G[len] = S[len];
    }

 

cmp를 확인해보면 G[a]와 G[b]를 비교하여 R이 정렬이 된다. 

G에 저장되어 있는 수를 기반으로 R의 값들의 위치가 재설정 되는 것이다.

 

bool cmp(int a, int b) {
    if (G[a] == G[b]) return G[a + t] < G[b + t];
    return G[a] < G[b];
}

std::sort(R, R + len, cmp);

 

TG를 재설정하기 위한 작업이다. R[i-1]과 R[i]를 비교하여 만약 비교가 된다면 전 그룹보다 +1이 되어야 하고, 비교가 되지 않는다면 동일 그룹으로 설정해줘야 한다. 그렇기 때문에 RG[R[i]] = TG[R[i-1]]를 해주는 것이다.

TG[R[0]] = 0;
for (int i = 1; i < len; i++) {
    if (cmp(R[i - 1], R[i])) TG[R[i]] = TG[R[i-1]] + 1;
    else TG[R[i]] = TG[R[i - 1]];
}

 

G의 재설정과 t의 *2배를 통해 logn에 가능하다는 것을 보여준다.

for (int i = 0; i < len; i++) G[i] = TG[i];
t *= 2;

 

솔직히 지금 내가 글을 썼는데 이 글을 보고 이해할 수 있는 사람이 있을까 싶다. 나도 아직 완벽하게 이해가 되지는 않은것 같고, 이 알고리즘을 활용한 문제 풀이가 생긴다면 더 보완하도록 하겠다.