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)이다.

2.1보조 정리#

S_i = S_j이고 i가 L형, j가 S형이면 suf(i) < suf(j)이다.

c = S_i로 두자. i부터 c가 a번 반복된 뒤 처음으로 다른 문자 d가 온다. 같은 문자가 이어지는 동안 유형이 전파되므로 반복 구간은 전부 L형이고, 따라서 d < c이다 ($도 c보다 작으므로 이 경우에 포함된다). 마찬가지로 j부터 c가 b번 반복된 뒤 처음으로 다른 문자 e가 오고, 반복 구간이 전부 S형이므로 e > c이다. a ≤ b이면 두 접미사는 위치 a에서 처음 갈리는데 suf(i) 쪽 문자는 d, suf(j) 쪽 문자는 c(a < b일 때) 또는 e(a = b일 때)이고 d < c < e이므로 suf(i) < suf(j)이다. a > b이면 위치 b에서 c < e이므로 suf(i) < suf(j)이다. ■

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 위치들을 각 버킷의 끝 영역에 임의 순서로 배치하고 유도 정렬을 실행한다. 초기 배치에서 LMS 위치 p가 왼쪽에서 몇 번째인지를 ρ_p라 하자. 배치가 버킷 순서를 따르므로 ρ는 S_p 오름차순을 따른다.

lms(i) = min{ p > i : p는 LMS }로 두고, 위치 i의 비교 기준 κ(i)를 (문자, 유형) 쌍의 열로 정의한다.

κ(i) = ((S_i, τ_i), (S_i+1, τ_i+1), ⋯, (S_lms(i), S), ρ_lms(i))

τ_i ∈ {L, S}는 i의 유형이다. 쌍은 문자를 먼저 비교하고, 문자가 같으면 L < S로 비교한다. 마지막 성분 ρ는 쌍의 열이 완전히 같을 때만 비교된다. 열은 첫 LMS, 즉 L 뒤에 처음 오는 S에서 끝나므로, 두 열이 짧은 쪽 전체에서 일치하면 짧은 쪽 끝의 L 다음 S 패턴이 긴 쪽에도 나타나 긴 쪽 열도 같은 곳에서 끝난다 — 한쪽이 다른 쪽의 진접두사인 경우는 없다. 위치 n−1($)은 lms가 없고 항상 SA의 첫 칸을 차지한다.

유도 정렬이 끝나면 SA의 모든 위치가 κ 오름차순으로 정렬된다. 이것이 아래에서 증명할 성질이다.

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에 배치됨#

L형 위치를 큰 인덱스부터 본 것에 대한 귀납법을 사용한다. i보다 큰 모든 L형 위치가 SA에 배치됨을 귀납 가설로 두고, L형 위치 i도 언젠가 배치됨을 보인다.

기저 (가장 큰 L형 위치): i보다 큰 L형 위치가 없으면 i+1은 L형일 수 없다. i가 L형이므로 S_i > S_i+1이고 i+1은 S형이므로, i+1은 LMS 위치다. LMS 위치는 초기에 배치되므로 i도 배치된다.

귀납 (그 외 L형 위치): i+1의 유형에 따라 나눈다.

• 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같은 버킷 내 순서가 올바름#

L형 유도 동안 SA에 있는 항목은 초기 배치된 LMS 항목과 이미 배치된 L형 항목뿐이다. LMS 항목 p의 키를 κ̂(p) = ((S_p, S), ρ_p)로 읽으면 — L형 위치의 κ가 lms에서 정확히 이 꼬리로 끝나므로 κ와 정합한다 — 배치된 모든 항목이 항상 키 오름차순임을 배치 순서에 대한 귀납법을 사용한다.

기저 (초기 배치): LMS 항목끼리는 첫 문자가 버킷 순서이고, 같은 버킷 안에서는 ρ가 곧 배치 순서이므로 κ̂ 오름차순이다.

귀납 (L형 위치 i의 배치): 이미 배치된 항목 x와 i의 순서가 올바름을 보인다. S_i ≠ S_x이면 버킷이 다르므로 성립한다. S_i = S_x = c이면 두 경우로 나뉜다.

• x가 LMS 항목: κ(i)는 (c, L), κ̂(x)는 (c, S)로 시작하므로 κ(i) < κ̂(x)이다. 버킷 안에서 L형 항목은 head가 앞에서부터 채우고 LMS 항목은 끝 영역에 있으며, 버킷 크기 = (L형 수) + (S형 수)이고 LMS는 S형이므로 두 영역은 겹치지 않는다. 따라서 i는 x보다 왼쪽에 놓인다.
• x가 L형 항목: 첫 쌍 (c, L)이 같으므로 κ의 비교는 i+1과 x+1의 키 비교로 넘어간다. i+1과 x+1은 i, x보다 먼저 SA에 있었고 귀납 가설에 의해 키 순서대로 놓여 있다. 스캔은 왼쪽부터 진행하고 같은 버킷에서는 먼저 유도된 항목이 왼쪽에 놓이므로, i와 x의 배치 순서는 i+1과 x+1의 키 순서와 일치한다. ■

4.2.2S형 유도#

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

S형 위치를 큰 인덱스부터 본 것에 대한 귀납법을 사용한다. i보다 큰 모든 S형 위치가 SA에 배치됨을 귀납 가설로 두고, S형 위치 i도 배치됨을 보인다.

기저 (i = n − 1): 위치 n−1은 $이고 LMS 위치이므로 초기에 배치된다.

귀납 (그 외 S형 위치): i+1의 유형에 따라 나눈다.

• 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같은 버킷 내 순서가 올바름#

S형 유도가 끝나면 모든 S형 위치가 재배치되고, L형 항목은 L형 유도가 확정한 κ 순서의 위치에 남아 있다. 배치된 항목 전체가 κ 오름차순임을 배치 순서에 대한 귀납법을 사용한다.

S형 위치 i가 배치될 때, 이미 위치가 확정된 항목 x와의 순서를 본다. S_i ≠ S_x이면 버킷 순서로 성립한다. S_i = S_x = c이면 두 경우로 나뉜다.

• x가 L형 항목: κ(x)는 (c, L), κ(i)는 (c, S)로 시작하므로 κ(x) < κ(i)이다. 버킷 안에서 L형 항목은 앞 영역, S형 항목은 tail이 채우는 뒤 영역에 있고 두 영역은 겹치지 않으므로 x가 왼쪽이다.
• x가 S형 항목: 첫 쌍 (c, S)가 같으므로 κ의 비교는 i+1과 x+1의 키 비교로 넘어간다. i+1과 x+1은 i, x보다 먼저 확정되었고 귀납 가설(L형이면 L형 유도의 결과)에 의해 κ 순서대로 놓여 있다. 스캔은 오른쪽부터 진행하고 같은 버킷에서는 먼저 유도된 항목이 오른쪽에 놓이므로, i와 x의 순서는 i+1과 x+1의 키 순서와 일치한다. ■

5알고리즘#

1. 모든 위치를 S/L형으로 분류하고 LMS 위치를 구한다.
2. LMS 위치를 임의 순서로 각 버킷 끝에 배치하고 유도 정렬한다. LMS 위치 p의 κ(p)의 쌍 열은 정확히 p의 LMS 부분 문자열 구간이고 유형 열은 문자 열로 결정되므로, 정렬 후 LMS 위치들은 LMS 부분 문자열의 사전순으로 늘어서고 같은 부분 문자열끼리는 (ρ 순서로) 인접한다.
3. LMS 부분 문자열에 순위를 부여한다. 모든 LMS 부분 문자열이 서로 다르면 LMS 접미사 순서가 확정된다.
4. 같은 LMS 부분 문자열이 있으면 LMS 부분 문자열 순위로 축소 문자열 r을 구성하고 SA-IS를 재귀 호출해 LMS 접미사 순서를 구한다.
5. LMS 위치를 LMS 접미사 순서로 배치하고 유도 정렬하면 올바른 SA가 된다. 이때 κ 순서는 접미사 순서와 일치한다: 두 접미사는 κ의 쌍 열 안에서 갈리거나 (문자가 다르면 그대로, 문자가 같고 유형이 다르면 위 보조 정리에 의해 L형 쪽이 작다), 쌍 열이 완전히 같으면 비교가 다음 LMS 접미사의 비교로 넘어가는데 그 순서가 곧 ρ다.

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.