[Algorithm] 20 문자열 - 8
멘버 마이어스 알고리즘 구현
다음과 같은 배열 group [] 을 만든다.
접미사들을 맨 앞에서부터 순회하면서 각 접미사에 그룹 번호를 부여한다.
첫 접미사에는 항상 그룹 번호 0번을 부여한다.
그 이후부터는 이전 접미사와 첫 글자가 같으면 이전 접미사의 그룹 번호를 부여한다.
아니라면 이전 접미사의 그룹 번호에 1을 더한 번호를 부여한다.
첫 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(nlogn) 시간에 정렬할 수 있다.
그러고 나면 다시 이들을 순회하면서 O(n) 시간에 그룹을 지을 수 있다.
첫 t글자로 묶인 그룹 정보를 이용해 첫 2t글자를 비교하는 비교자의 구현
// 각 접미사들의 첫 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];
}
};
위 코드에서 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;
// 결과적으로 접미사 배열이 될 반환 값. 이 배열을 log(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(n | logn)의 시간이 걸리는 정렬이 지배하므로 전체 시간 복잡도는 O(n | log²n)이 된다. |
맨버-마이어스 알고리즘(suffix array) - t가 2의 지수승으로 늘어나는 이유
맨버 마이어스 알고리즘을 공부할때 반드시 궁금해야 할, 또한 알아야 할것이 있다. 왜 비교하는 기준인 t가 2의 지수승으로 늘어나게 되는가, 즉 왜 t는 1 , 2, 4, 8, 16의 형태로 늘어나게 되는가에 대한 것이다.
장담컨데 구글에는 쉽게 설명되있는 자료가 단 1개도 없다.. 본인이 맨버 마이어스를 굳이 포스팅한 이유가 바로 이것때문이다. 혹시 본인처럼 이유를 알지못해 고통스러워할 누군가가 반드시 있을거라고 생각하기 때문이다.
사실 t가 2의 지수승으로 늘어나게 되는 이유는 이 알고리즘을 아주 잘 이해 했다면 생각보다 쉽게 이해할수도 있다. 다만 제대로 된 설명을 못 듣고 그냥 이런 알고리즘이다! 라는 식으로 배웠다면, 알고리즘을 아무리 잘 이해했어도 왜 t가 2의 지수승으로 늘어나는지에 대해선 모를수도 있다. 꽤 시간을 들여 곰곰히 생각해보아야 한다.
본문으로 돌아와서 왜 t는 1, 2, 4, 8, 16, 32 만을 지정하는 것일까….??? 한번 나름대로 생각해보자.
……
생각해 보았는가?? 그렇다면 이젠 한번 반대로 생각해보자
그렇다면 혹시 건너뛰게 되는 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 18, … 번째에 대한 것들은 이미 검사가 돼있는 것일까?? (이렇게 생각을 하는 순간 절반을 이해한 것이다. 조금만 힘내서 끝까지 읽어 보자)
사실 정말 그렇다.
당신도 모르는 사이(??)에 3, 5, 6, 7, 9, 10 … 에 대한 것들이 모조리 검사가 되어있기 때문이다.
무슨 말도 안되는 말일까 싶지만, 정말 그렇다. 그렇기 때문에 이미 검사된 3, 5, 6, 7, 9… 에 대한것들은 건너뛰고 편하게 1, 2, 4, 8, 16 에 대한 것들만 비교하면서 검사하면 되는 것이며, 이 아이디어는 이 알고리즘의 ‘핵심’이 된다(엄밀하게 말하면 시간 복잡도를 줄이는것의 핵심이 됨).
그런데 어떻게 미리 검사가 된 걸까?? 코드내에서 거들떠도 보지않은 3, 5, 6, 7.. 에 대한 것들은 도대체 어느 시점에, 어떠한 방식으로 검사가 되었다는 소리일까?? 지금부터 차근차근 알아가보자.
미지의 문자 x(i)로 이루어진 문자열이 있다고 해보자. 길이는 n이다.
이때 문자열은 다음과 같다.
x0x1x2x3x4x5x6x7x8……..xn
이 문자열의 접미사들은 다음과 같다.
x0x1x2x3x4x5x6x7x8……..xn
x1x2x3x4x5x6x7x8……..xn
x2x3x4x5x6x7x8……..xn
:
생략
:
xn (마지막 접미사)
이 문자들의 그룹을 나눠보자 먼저 접미사의 첫글자를 기준으로 나눠보자. (참고로 각각의 미지문자는 본인이 아무렇게나 상정해서 나눈것임을 알아두자…)
그렇게 되면 각 접미사들의 가장 첫 번째 문자들에 대해선 그 위치가(그룹에대한) 모조리 ‘검증’ 되엇다고 할수 있다.
검증된 문자들을 표시해 보자
이번엔 접미사의 두번째 글자를 기준으로 그룹을 만들어 보자 참고로 이때의 t는 1이다.
이렇게 되면 두번째 문자까지 ‘검증’되었음을 알수있다. 마찬가지로 한번 표시해 보자.
이 그루핑이 끝나고 나면 t는 함수정의에 의해 2가 된다.
그런데 한번 자세히 자세히 살펴보자 저렇게 표시하고 나니 뭔가 보이는 것 같지 않은가??(안보여도 된다 ㅎㅎ)
이 시점에서 다시한번 comp 함수를 살펴보자
bool comp(int i, int j) { if (group[i] != group[j]) return group[i] < group[j]; return group[i + t] < group[j + t]; }
group[i + t] < group[j + t]; 가 보여주고 있듯이, 대소비교를 하는 것은 suffix[i +t] 와 suffix[j + t]를 비교하는 것이 아니다. 여기서 비교를 하고있는 것은, suffix i + t 와 suffix j + t가 해당하는 그룹의 번호로 대소비교를 하고 있는 것이다.
그렇다면 현재 위의 그룹상태에서 그룹 1번에 있는 x3x4x5…xn 와 x6x7x8…xn 의 대소비교를 살펴보자.
위 접미사에서 x3와 x4 그리고 x6와 x7은 각각 검증 되어져 있는 상태이다.
따라서 첫번째 조건문 if (group[i] != group[j])으로 진입할수 없게되고, group[i + t] < group[j + t];
를 반환하게 된다. 그런데 i + t, j + t는 현재 suffix 3 + 2와 suffix 6 + 2를 나타내게 되고
결론적으로는 suffix5와 suffix8이 속한 그룹번호를 비교하게 된다..
그런데 이 두 접미사 x5x6x7…xn 과 x8x9x10….xn의 앞 두문자도 다른 모든 접미사와 마찬가리로
이미 검증이 완료된 문자다.
따라서 이것을 비교하는 순간 suffix3, x3x4x5….xn의 입장에서는 x5뿐만 아니라 x6까지 함께 검증해버린 셈이 되는 것이다. (이시점 까지 잘 이해했 다면 이제 확실히 이해 할수 있게 된다)
따라서 t가 2인 상태에서 그룹핑을 하게 되면 다음과 같이 표시할수 있게 된다.
그리고 t는 4가 된다.
아마도 거진 이해가 되겟지만 마지막으로 이상태에서 한번만더 그룹핑을 해보자.
그룹번호 5번에 속해있는 x2x3x4x5…xn 과 x7x8x9x10…xn 을 비교한다고 해보자.
그렇게 되면 서로 같은 그룹에 있으므로 suffix 2 + 4 와 suffix7 + 4, 즉 suffix6이 속한 그룹번호와
suffix 11이 속한 그룹번호를 대소 비교하게 된다.
그런데 suffix 6이나 suffix 11 즉, x6x7x8x9….xn과 x11x12x13x14….xn도 다른 모든 suffix들과 마찬가지로
4번째 문자 까지 검증이 완료된 상태다. 따라서 이둘의 비교를 해주는 순간
x2x3x4x5….xn의 입장에서는 추가로 x6x7x8x9의 검증까지 한꺼번에 해주는 것이 된다.
다시말해 x2x3x4x5x6x7x8x9….xn 이 되고 x7x8x9x10x11x12x13x14…xn 이 되는 것이다.
t가 4일때는 무려 한꺼번에 4개를 동시에 검증하는것과 같은 효과를 가져오는 것이다.
이렇게 되면 우리는 알수있다. 이를 계속 반복한다고 했을때 위와 같은 이유로 검증한 영역은 계속 2배씩 늘어나게 되고, 따라서 1, 2, 4, 8, 16..에 대한 부분만 검사해 주면 되는 것이다.
정말 쉽게 풀어써서 누구라도 알수있게 해보자! 라는 마음가짐으로 포스팅을 해보았는데… 생각만큼 잘된것 같지는 않다.. 아마도 이 글을 봐도 이해 못하는 사람이 많을거 같다는 예감이 든다… 개념을 글로써 이해하기 쉽게 작성하는 작업은 장말이지 쉬운것이 아님을 새삼깨닫는다. 혹, 이해가 안가더라도 한번 천천히 차근차근 생각해보자. 댓글이나 이메일로 질문 또는 지적은 언제나 대 환영이다. 혹시 글을 읽으면서 이해가 안되거나, 틀린부분이 있거나, 아예 이 글자체가 엉터리라 생각되거나, 물어볼것이 있다면 언제든지 댓글 달아주길 바란다. 이 블로그는 언제나 열려있다.
결론적으로는 현재 비교하려는 접미사 뒤쪽의 문자열 부분도 이미 t만큼 비교가 되어있어서 그 정보를 이용한다는 뜻이군요..접미사의 접두사가 다른 접미사에도 존재한다는 Suffix Array 특성 때문에 가능한거네요..