접미사 배열

Suffix array en:Suffix array {| class="infobox" | 접미사 배열 |- ! 유형 | colspan="2" | 배열 |- ! 고안자 ! colspan="2" ! 1990 |- ! colspan="3" class="navbox-abovebelow" | 빅 오 표기법에 따른
시간 복잡도 |- | | 평균 | 최악 |- ! 공간 | \mathcal{O}(n) | \mathcal{O}(n) |- ! 구성 | \mathcal{O}(n) | \mathcal{O}(n) |} 컴퓨터 과학에서 **접미사 배열**, 또는 **서픽스 어레이**(suffix array)이란 어떤 문자열의 접미사를 사전식 순서대로 나열한 배열을 말한다. 문자열 검색이나 전문 검사 등에 쓰인다.
# 정의
길이가 n인 문자열 S = S[1]S[2]...S[n]이 있다고 하자. 이때 S[1], S[2], …, S[n]은 문자열 S를 구성하는 문자이다. 그리고 S[i,j]는 S의 i번째 문자부터 j번째 문자까지의 부분 문자열이라고 하자. 문자열 S에 대한 접미사 배열 A는 S의 접미사들을 사전식 순서로 정렬했을 때 접미사의 시작 위치를 저장한 정수 배열이다. 즉, A[i]에 저장된 내용은 S의 접미사 중 사전순으로 i번째인 것의 시작 위치이다. 달리 말하자면, 1 \leq i \leq n인 i에 대해 사전순으로 S[A[i],n] < S[A[i+1],n]이 성립한다.
# 예시
색인할 문자열 S = `banana`가 있다고 하자. {| class="wikitable" |- ! 표 왼쪽 제목 | i | 1 || 2 || 3 || 4 || 5 || 6 || 7 |- ! 표 왼쪽 제목 | S[i] | b || a || n || a || n || a || $ |} 문자열의 끝은 사전순으로 어떠한 문자보다 앞서기 때문에 `$`라는 특수 문자로 표시한다. 이때 문자열 S의 접미사들은 시작 인덱스를 i라고 할 때 다음과 같이 나타낼 수 있다. {| class = "wikitable" ! align = "left" | 접미사 !! align = "left" | i |- class = "odd" | align = "left" | banana$ || align = "left" | 1 |- class = "even" | align = "left" | anana$ || align = "left" | 2 |- class = "odd" | align = "left" | nana$ || align = "left" | 3 |- class = "even" | align = "left" | ana$ || align = "left" | 4 |- class = "odd" | align = "left" | na$ || align = "left" | 5 |- class = "even" | align = "left" | a$ || align = "left" | 6 |- class = "odd" | align = "left" | $ || align = "left" | 7 |} 그리고 접미사들을 다음과 같이 오름차순으로 정렬할 수 있다. {| class = "wikitable" ! align = "left" | 접미사 !! align = "left" | i |- class = "odd" | align = "left" | $ || align = "left" | 7 |- class = "even" | align = "left" | a$ || align = "left" | 6 |- class = "even" | align = "left" | ana$ || align = "left" | 4 |- class = "even" | align = "left" | anana$ || align = "left" | 2 |- class = "odd" | align = "left" | banana$ || align = "left" | 1 |- class = "odd" | align = "left" | na$ || align = "left" | 5 |- class = "odd" | align = "left" | nana$ || align = "left" | 3 |} 이때 접미사 배열 A는 위와 같이 정렬된 접미사의 시작 위치를 저장한 배열이다. j를 접미사 배열 A의 인덱스라고 할 때 A는 다음과 같다. {| class = "wikitable" !표 왼쪽 제목 | j | 1 || 2 || 3 || 4 || 5 || 6 || 7 |- !표 왼쪽 제목 | A[j] | 7 || 6 || 4 || 2 || 1 || 5 || 3 |} A의 각 원소에 대응되는 접미사를 가로로 나열하면 다음과 같다. {| class = "wikitable" ! align = "left" | j !! align = "left" | A[j] !! align = "left" | 해당하는 접미사 |- class = "odd" | 1 || 7 || align = "left" | $ |- class = "even" | 2 || 6 || align = "left" | a$ |- class = "even" | 3 || 4 || align = "left" | ana$ |- class = "even" | 4 || 2 || align = "left" | anana$ |- class = "odd" | 5 || 1 || align = "left" | banana$ |- class = "odd" | 6 || 5 || align = "left" | na$ |- class = "odd" | 7 || 3 || align = "left" | nana$ |} 예를 들어, A[3]에는 4라는 값이 저장되어 있는데, 이는 S의 접미사를 사전순으로 정렬했을 때 세 번째에 위치하는 접미사가 시작 인덱스가 4인 `ana$`라는 의미이다. 접미사 배열을 만들면 빈 문자열이 항상 처음에 오게 됨을 알 수 있다. 즉, 빈 문자열으로부터 얻을 수 있는 정보가 없기 때문에 빈 문자열을 생략할 수 있다.
# 접미사 배열을 구현하는 알고리즘

## 나이브한 알고리즘
{| class="infobox" |- ! 시간 복잡도 | \mathcal{O}(n^2\lg n) |- ! 공간 복잡도 | \mathcal{O}(n) |} 접미사 배열을 만드는 가장 쉬운 방법은 비교 정렬 알고리즘을 사용하는 것이다. 문자열의 길이를 n라고 할 때 접미사는 n개가 만들어지므로 정렬에 필요한 비교 횟수는 점근표기법으로 \mathcal{O}(n\lg n)으로 나타낼 수 있다. 두 문자열을 사전순으로 정렬하는 가장 빠른 방법은 모든 문자에 대해 순서를 비교하는 것이므로 접미사의 최대 길이인 \mathcal{O}({n})번의 비교를 통해 두 접미사를 비교할 수 있다. 접미사끼리 비교하는 횟수는 \mathcal{O}(n \lg n)이고, 한 쌍의 접미사의 사전 순서를 판단하는데 필요한 비교 횟수는 \mathcal{O}({n})이므로 총 시간 복잡도는 \mathcal{O}({n}^{2} \lg n)이 된다.
## Manber-Myers 알고리즘
{| class="infobox" |- ! 시간 복잡도 | \mathcal{O}({n}\lg{n}) |- ! 공간 복잡도 | \mathcal{O}(n) |} Manber-Myers 알고리즘은 정렬할 때 **랭크**라는 개념과 **기수 정렬**을 사용하여 시간 복잡도를 줄인 알고리즘이다. 이 알고리즘은 접미사 배열을 구하는 다양한 알고리즘 가운데 프로그래밍 대회에서 자주 사용되는데, 시간 복잡도가 더 작은 알고리즘은 짧은 시간 안에 구현하기 어렵기 때문이다. 이 알고리즘은 여러 단계의 정렬을 통해 전체 접미사를 정렬한다. Manber-Myers 알고리즘을 다음과 같이 개략적으로 설명할 수 있다. # 문자열 S의 접미사들을 첫 번째 글자와 두 번째 글자에 대해 사전순으로 정렬한다. # 정렬된 순서를 바탕으로 랭크를 부여한다. # 접미사의 특성을 이용하여 부여된 두 개의 랭크를 기준으로 정렬한다. (비교 범위가 두 배가 된다.) # 2로 돌아간다.
### 랭크
랭크는 정렬을 위해 정한 일정한 기준으로, 어떤 접미사에서 접두사를 빼도 접미사인 성질을 응용한 것이다. Manber-Myers 알고리즘에서는 각 단계마다 접미사에 랭크를 부여하고, 랭크를 기준으로 정렬을 한다. k번째 단계에서 사용되는 랭크는 접미사의 앞에서 2^{k-1}글자의 순서 정보를 담고 있다. 랭크를 기준으로 수행을 할 때마다 비교 범위는 두 배가 되므로 접미사에 대해 \mathcal{O}(\lg n)단계를 거치게 된다. 그리고 각 단계마다 랭크를 부여하고 정렬하는 작업을 하는데, 랭크는 모든 원소를 순차적으로 확인하면서 구할 수 있으므로 시간 복잡도는 \mathcal{O}({n})이고, 비교 기반 정렬의 시간 복잡도는 \mathcal{O}(n\lg n)이므로 랭크를 기반으로 한 비교 기반 정렬을 사용하면 총 시간 복잡도는 \mathcal{O}(\lg{n}(n+n\lg{n})) = \mathcal{O}(n\lg^2{n})이 된다. 첫번째 단계에서는 참조할 기존의 랭크가 없기 때문에 첫 번째 랭크를 정하기 위한 사전 작업이 필요하다. 첫 번째 랭크는 접미사의 앞에서부터 2^0 = 1번째 글자의 정보를 가져야 하므로 첫 번째 글자에 대해 사전순으로 정렬한 뒤 첫 번째 랭크를 부여하면 된다. 랭크는 정렬된 순서에 따라 증가하는 어떠한 수여도 무관하지만, 일반적으로 다음과 같은 과정을 통해 연속된 자연수를 부여한다. # 비교하는 범위에 해당하는 문자가 없으면 -1을 부여한다. # 정렬된 배열에서 비교하는 범위에 대해 이전 인덱스(j-1)와 같으면 같은 랭크를, 다르면 1을 더한 랭크를 부여한다. 문자열 S = `banana`를 첫 번째 문자에 대해 정렬한 뒤 첫 번째 랭크를 부여한 결과는 다음과 같다. {| class="wikitable" ! align="left" | j !! align="left" | 접미사 !! align="left" | i !! align="left" | 첫 번째 글자 !! align="left" | 첫 번째 랭크 |- class="odd" | 0 || align="left" | $ || 7 || $ || -1 |- class="even" | 1 || align="left" | a$ || 6 || a || 0 |- class="even" | 2 || align="left" | ana$ || 4 || a || 0 |- class="even" | 3 || align="left" | anana$ || 2 || a || 0 |- class="odd" | 4 || align="left" | banana$ || 1 || b || 1 |- class="odd" | 5 || align="left" | na$ || 5 || n || 2 |- class="odd" | 6 || align="left" | nana$ || 3 || n || 2 |} 이때 j는 접미사 배열의 인덱스이고 i는 접미사가 시작되는 문자의 번호, 즉 접미사의 이름이다. 첫 번째 랭크는 접미사의 앞에서부터 2^0=1번째 자리까지를 비교한 정보이므로, 두 번째 자리를 비교한 정보를 이용하여 다음 랭크를 구할 수 있다. 그러나 모든 접미사에 대해 랭크가 부여되어 있으므로 두 번째 자리를 비교한 정보는 접미사 i+2^0의 랭크로 구할 수 있다. 이때 문자열이 끝나서 i+2^0 접미사가 없는 경우 모든 문자보다 앞서야 하므로 -1로 처리한다. 그러므로 i의 첫 번째 랭크와 접미사 i+2^0의 첫 번째 랭크를 기준으로 정렬한 뒤 두 번째 랭크를 부여할 수 있다. 두 번째 랭크 역시, i의 첫 번째 랭크와 i+2^0의 랭크가 이전 인덱스와 같으면 같은 랭크, 다르면 1을 더한 랭크로 부여한다. 첫 번째 랭크와 접미사 i+1의 랭크를 기준으로 구한 두 번째 랭크는 다음과 같다. {| class="wikitable" ! align="left" | j !! align="left" | 접미사 !! align="left" | i !! align="left" | i의 첫 번째 랭크 !! align="left" | i+2^0의 첫 번째 랭크 !! align="left" | 두 번째 랭크 |- class="odd" | 0 || align="left" | $ || 7 || -1 || -1 || -1 |- class="even" | 1 || align="left" | a$ || 6 || 0 || -1 || 0 |- class="even" | 2 || align="left" | ana$ || 4 || 0 || 2 || 1 |- class="even" | 3 || align="left" | anana$ || 2 || 0 || 2 || 1 |- class="odd" | 4 || align="left" | banana$ || 1 || 1 || 0 || 2 |- class="odd" | 5 || align="left" | na$ || 5 || 2 || 0 || 3 |- class="odd" | 6 || align="left" | nana$ || 3 || 2 || 0 || 3 |} 같은 방식으로 i와 i+2^1의 두 번째 랭크에 대해 정렬한 뒤 부여한 세 번째 랭크는 다음과 같다. {| class="wikitable" ! align="left" | j !! align="left" | 접미사 !! align="left" | i !! align="left" | i의 두 번째 랭크 !! align="left" | i+2^1의 두 번째 랭크 !! align="left" | 세 번째 랭크 |- class="odd" | 0 || align="left" | $ || 7 || -1 || -1 || -1 |- class="even" | 1 || align="left" | a$ || 6 || 0 || -1 || 0 |- class="even" | 2 || align="left" | ana$ || 4 || 1 || 0 || 1 |- class="even" | 3 || align="left" | anana$ || 2 || 1 || 1 || 2 |- class="odd" | 4 || align="left" | banana$ || 1 || 2 || 3 || 3 |- class="odd" | 5 || align="left" | na$ || 5 || 3 || -1 || 4 |- class="odd" | 6 || align="left" | nana$ || 3 || 3 || 3 || 5 |} 이와 같은 방식으로 비교 범위가 문자열의 길이 n보다 커질 때까지 반복하면 접미사 배열을 얻을 수 있다.
### 기수 정렬의 구체적인 방법
랭크의 크기는 최대 n이므로 두 번의 기수 정렬을 사용하여 시간 복잡도를 줄일 수 있다. 랭크가 구해진 상태에서 접미사 i+2^k의 랭크에 대해 기수 정렬을 하고 i의 랭크에 대해 한 번 더 기수 정렬을 하면 정렬을 \mathcal{O}(n)에 수행할 수 있다. Manber-Myers 알고리즘은 O(\lg{n})번의 단계를 거치므로, 기수 정렬을 사용하였을 때의 총 시간 복잡도는 \mathcal{O}(n\lg{n})이 된다.
## SA-IS 알고리즘
{| class="infobox" |- ! 시간 복잡도 | \mathcal{O}(n) |- ! 공간 복잡도 | \mathcal{O}(n) |} SA-IS 알고리즘은 다음 문자가 현재 문자보다 사전순으로 뒤인지 앞인지에 따라 문자열을 분류한 뒤, 여러 단계의 **추측**이라는 과정을 통해 접미사 배열을 구성한다.
# 응용
빈 문단
# 역사
접미사 배열은 원래 Gene Myers와 Udi Manber가 접미사 트리보다 메모리 소비를 줄이려고 개발하였다. 이 경향이 이어져 압축된 접미사 배열이나 압축 전문 인덱스 등이 개발되었다.