Suffix Array 개념 이해

아래 블로그를 보고 이해한 내용을 정리합니다.

 

blog.naver.com/kks227/221028710658

접미사 배열(Suffix Array) (수정: 2018-03-03)

// [출처] 접미사 배열(Suffix Array) (수정: 2018-03-03)|작성자 라이

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX = 1<<19;
 
char S[MAX];
int N, d, sa[MAX], pos[MAX]; // pos: 그룹 번호
 
// 접미사 비교에 사용할 비교 함수
bool cmp(int i, int j){
    // 먼저 자신의 위치의 문자를 비교
    if(pos[i] != pos[j]) return pos[i] < pos[j];
    // 문자가 같으면 d칸 뒤의 문자끼리 비교
    i += d;
    j += d;
    return (i < N && j < N) ? (pos[i] < pos[j]) : (i > j);
}
 
// S를 사용해 sa 배열을 만드는 함수
void constructSA(){
    N = strlen(S);
    // 전처리
    for(int i=0; i<N; i++){
        sa[i] = i;
        pos[i] = S[i]; // 제일 첫 번째 루프에서는 제자리 문자로 비교
    }
    // d를 2배씩 늘려가면서 매번 앞에서부터 d*2글자만 보고 접미사 정렬
    for(d=1; ; d*=2){
        sort(sa, sa+N, cmp);
 
        // temp: 새로운 그룹 번호
        int temp[MAX] = {0};
        // 앞에서부터 훑으면서 각 접미사가 서로 다른 그룹에 속할 때마다 그룹 번호 증가시킴
        for(int i=0; i<N-1; i++)
            temp[i+1] = temp[i] + cmp(sa[i], sa[i+1]);
        // pos 배열을 temp 배열로 대체
        for(int i=0; i<N; i++)
            pos[sa[i]] = temp[i];
 
        // 모든 접미사가 다른 그룹으로 나뉘어졌다면 종료
        if(temp[N-1] == N-1) break;
    }
}
 
int main(){
    scanf("%s", S);
    constructSA();
    for(int i=0; i<N; i++)
        printf("%d ", sa[i]+1);
}

 

d를 두배씩 곱하면서 어떻게 비교를 하는건지 정리합니다. 그림을 참고하면서 아래 글을 읽습니다.

예시 ) bacdebacd 로 d = 2까지 진행

 

 

1. 초기 상태는 앞 한글자만 그룹으로 지정을 해둔 상태입니다. ( 정렬되어 있지 않음 )

 

2. d = 1 일때 앞 한글자( 그룹 )이 같으면 다음 한글자( 그룹 )이 같은지 확인해서 정렬합니다.

  - 이게 가능한 이유는, 초기상태를 보면 모든 포지션에 대해서 앞 한글자를 그룹으로 지정해두었기 때문입니다.

 

3. 이 과정을 마치게되면 정렬된 상태가 앞 두글자를 그룹으로 묶습니다.

  - 위 사진에 d = 1 일때 temp에 파란색 글씨로 적어둔 글자를 기준으로 정렬되어있습니다.

 

4. d = 2 일 때 앞 두글자( 그룹 )이 같으면 다음 두글자( 그룹 )이 같은지 확인해서 정렬합니다.

 - 여기서 d = 1 일 때 0으로 같은 그룹이엇던 1, 6 인덱스가 0, 1 로 다른 그룹으로 나뉘는 것을 이해하면 됩니다.

 - idx 1 : ac, idx3 : de
 - idx 6 : ac, idx8 : d

 - 이전에 앞 두글자로 그룹을 묶었기 때문에, idx에 2를 더한 값으로 비교를하면 총 네글자로 비교하게 됩니다.

 

5. 위와 같은 과정을 반복하면

 - 8글자를 비교할때는 4글자 그룹 + 4글자 그룹

 - 16글자를 비교할때는 8글자 그룹 + 8글자 그룹

 - ..

 - 2^N글자를 비교할때는 2^(N - 1)글자 그룹 + 2^(N - 1)글자 그룹

 - 으로 비교할 수 있습니다