SA-IS

1개요#

SA-IS는 O(n) 접미사 배열 구성 알고리즘이다.

2S/L형 분류#

시작하기 전에 문자열 마지막에 다른 모든 문자보다 작은 특수 문자 $를 덧붙인다.

각 위치 i를 다음 규칙으로 S형 또는 L형으로 분류한다.

• S_i < S_i+1, 또는 S_i = S_i+1이고 i+1이 S형 ⇒ i는 S형(Small)
• S_i > S_i+1, 또는 S_i = S_i+1이고 i+1이 L형 ⇒ i는 L형(Large)
• $는 S형

오른쪽에서 왼쪽으로 스캔하면 O(n)에 분류할 수 있다. i가 S형이면 suf(i) < suf(i+1), L형이면 suf(i) > suf(i+1)이다.

3LMS 위치#

바로 왼쪽이 L형인 S형 위치를 LMS(Left-Most S-type) 위치라 한다. $는 항상 LMS다.

LMS 위치 i의 LMS 부분 문자열은 i에서 시작해 다음 LMS 위치 j까지의 구간 S_i⋯j이다. 두 LMS 위치 사이에 다른 LMS 위치, 즉 L→S 전환이 없으므로, 구간 내부는 S형 연속 뒤 L형 연속으로 이루어지고 j에서 S형으로 끝난다(S⁺L⁺S 패턴).

두 LMS 부분 문자열이 같으려면 길이가 같고 대응하는 각 위치의 문자와 S/L형이 모두 일치해야 한다.

4유도 정렬#

문자 c로 시작하는 접미사들의 위치 집합 B_c = { i : S_i = c }를 버킷이라 한다. SA에서 B_c는 연속 구간을 차지한다. SA를 정확히 몰라도 버킷은 쉽게 알 수 있다.

초기에 SA의 모든 위치가 비어 있다. lms(i)를 i의 오른쪽 첫 LMS 위치라 하자. LMS 위치들을 각 버킷 끝에 배치하고 유도 정렬을 실행하면 모든 위치 i가 비교 기준 (S_i, S_i+1, ⋯, S_lms(i)−1, r_lms(i))으로 정렬된다.

4.1알고리즘#

L형 유도: 각 버킷의 맨 앞에 삽입 포인터 head_c를 두고, i = 0, ⋯, n−1 순서로 스캔한다. SA_i가 비어 있으면 건너뛰고, SA_i = j이면 j−1이 L형일 때 j−1을 head_Sj−1에 삽입하고 head_Sj−1를 오른쪽으로 한 칸 이동한다.

S형 유도: 각 버킷의 맨 뒤에 삽입 포인터 tail_c를 두고, i = n−1, ⋯, 0 순서로 스캔한다. SA_i가 비어 있으면 건너뛰고, SA_i = j이면 j−1이 S형일 때 j−1을 tail_Sj−1에 삽입하고 tail_Sj−1를 왼쪽으로 한 칸 이동한다. 이때 빈 칸에 삽입될 수도 있고, 이미 채워진 칸을 덮어쓸 수도 있다. LMS 위치는 S형이므로 초기에 배치한 LMS 항목들은 이 과정에서 S형 위치로서 재삽입된다.

4.2증명#

4.2.1L형 유도#

4.2.1.1모든 L형 위치가 SA에 배치됨#

i < j인 모든 j에 대해 j가 L형 위치일 경우 SA에 배치됨을 가정하고 i가 L형 위치일 경우 언젠가 SA에 배치됨을 보이자.

• i+1이 LMS 위치: LMS 위치는 초기에 배치되어 있으므로 i도 배치된다.
• i+1이 L형 위치이고 S_i+1 > S_i+2: i+1은 i+2가 스캔될 때 배치되는데, i+1은 i+2보다 오른쪽 버킷에 배치되므로 언젠가 스캔되어 i가 배치된다.
• i+1이 L형 위치이고 S_i+1 = S_i+2: S_i+1 = S_i+2이므로 i+2도 L형이다. 가정에 의해 i+2가 SA에 배치된다. i+2가 배치될 때 head_Si+1는 i+2의 위치를 지나 전진하며 이후 오른쪽으로만 이동한다. 따라서 i+2가 스캔될 때 i+1은 i+2보다 오른쪽에 배치되어 이후 스캔되고 i가 배치된다.

4.2.1.2같은 버킷 내 순서가 올바름#

SA 위치 0, 1, ⋯, k−1 중 L형 위치가 모두 올바르게 정렬되어 있다고 가정하자.

i, j ≤ k, S_i = S_j = c이고 suf(i) < suf(j)인 L형 위치 i, j를 생각하자. S_i = S_j이므로 suf(i+1) < suf(j+1)이고, 가정에 의해 i+1이 j+1보다 왼쪽에 있다. 따라서 i가 j보다 먼저 배치되고, SA 위치 0, 1, ⋯, k 중 L형 위치가 모두 올바르게 정렬되어 있다. ■

4.2.2S형 유도#

4.2.2.1모든 S형 위치가 SA에 배치됨#

j > i인 모든 S형 위치 j가 SA에 배치됨을 가정하고 S형 위치 i가 SA에 배치됨을 보이자.

• i+1이 L형: L형 유도 후 i+1이 SA에 배치되어 있다. i+1이 스캔될 때 i가 배치된다.
• i+1이 S형이고 S_i+1 < S_i+2: i+1은 i+2가 스캔될 때 배치되는데, i+1은 i+2보다 왼쪽 버킷에 배치되므로 이후 스캔되어 i가 배치된다.
• i+1이 S형이고 S_i+1 = S_i+2: S_i+1 = S_i+2이므로 i+2도 S형이다. 가정에 의해 i+2가 SA에 배치된다. i+2가 배치될 때 tail_Si+1는 i+2의 위치를 지나 후퇴하며 이후 왼쪽으로만 이동한다. 따라서 i+2가 스캔될 때 i+1은 i+2보다 왼쪽에 배치되어 이후 스캔되고 i가 배치된다.

4.2.2.2같은 버킷 내 순서가 올바름#

SA 위치 n−1, n−2, ⋯, k+1 중 S형 위치가 모두 올바르게 정렬되어 있다고 가정하자.

i, j ≥ k, S_i = S_j = c이고 suf(i) < suf(j)인 S형 위치 i, j를 생각하자. S_i = S_j이므로 suf(i+1) < suf(j+1)이고, 가정에 의해 i+1이 j+1보다 왼쪽에 있다. 따라서 j가 i보다 먼저 배치되고, SA 위치 n−1, n−2, ⋯, k 중 S형 위치가 모두 올바르게 정렬되어 있다. ■

5알고리즘#

1. 모든 위치를 S/L형으로 분류하고 LMS 위치를 구한다.
2. LMS 위치를 S_i 순서로 배치하고 유도 정렬한다. SA에서 LMS 위치들의 상대 순서는 LMS 부분 문자열의 정렬 순서와 일치한다.
3. LMS 부분 문자열에 순위를 부여한다. 모든 LMS 부분 문자열이 서로 다르면 LMS 접미사 순서가 확정된다.
4. 같은 LMS 부분 문자열이 있으면 LMS 부분 문자열 순위로 축소 문자열 r을 구성하고 SA-IS를 재귀 호출해 LMS 접미사 순서를 구한다.
5. LMS 위치를 LMS 접미사 순서로 배치하고 유도 정렬하면 올바른 SA가 된다.

LMS 위치 수는 ⌊n/2⌋ 이하이므로 |r| ≤ n/2. T(n) = T(n/2) + O(n) ⇒ T(n) = O(n).

6증명#

축소 문자열의 SA가 LMS 부분 접미사 순서를 올바르게 구함을 보이자.

LMS 위치를 순서대로 p₀ < p₁ < ⋯ < p_m-1이라 하고, r_k를 p_k의 LMS 부분 문자열에 부여한 rank라 한다. 축소 문자열 r = (r₀, r₁, ⋯, r_m-1)의 k번째 접미사를 suf_r(k)로 쓴다.

suf_r(k) < suf_r(j) ⇒ suf_S(p_k) < suf_S(p_j)임을 보이자.

r_k+i < r_j+i인 최소의 음이 아닌 정수 i를 잡는다. 순위가 같은 LMS 부분 문자열은 완전히 같으므로 suf_S(p_k)와 suf_S(p_j)의 비교는 결국 suf_S(p_k+i)와 suf_S(p_j+i)의 비교가 된다.

두 LMS 부분 문자열은 다음 성질을 만족한다.

• 접두사 관계는 불가능하다. LMS 부분 문자열은 정확히 다음 LMS 위치에서 끝난다. 짧은 쪽의 끝이 긴 쪽의 내부에 있으려면 그 위치가 LMS여야 하는데, LMS 사이에 LMS가 없으므로 모순이다.
• 문자 배열이 같으면 S/L형도 같다. LMS 부분 문자열의 S/L형은 문자 배열과 일대일 대응이다.

따라서 두 LMS 부분 문자열이 다르면 반드시 어떤 위치에서 문자가 다르다. 처음으로 문자가 다른 위치 q에서 S_pk+i+q < S_pj+i+q이므로 suf_S(p_k+i) < suf_S(p_j+i)이고, suf_S(p_k) < suf_S(p_j)이다.

따라서 r의 접미사 배열이 LMS 접미사의 순서를 정확히 결정한다. ■

7참고 문헌#

• Nong, G., Zhang, S., & Chan, W. H. (2009). Linear suffix array construction by almost pure induced-sorting. 2009 Data Compression Conference, 193–202.