접미사 배열

컴퓨터 과학에서 **접미사 배열**, 또는 **서픽스 어레이**()이란 어떤 문자열의 접미사를 사전식 순서대로 나열한 배열을 말한다. 문자열 검색이나 전문 검사 등에 쓰인다.

## 정의

길이가 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 = `banana`가 있다고 하자.

문자열의 끝은 사전순으로 어떠한 문자보다 앞서기 때문에 `$`라는 특수 문자로 표시한다. 이때 문자열 S의 접미사들은 시작 인덱스를 i라고 할 때 다음과 같이 나타낼 수 있다.

그리고 접미사들을 다음과 같이 오름차순으로 정렬할 수 있다.

이때 접미사 배열 A는 위와 같이 정렬된 접미사의 시작 위치를 저장한 배열이다. j를 접미사 배열 A의 인덱스라고 할 때 A는 다음과 같다.

A의 각 원소에 대응되는 접미사를 가로로 나열하면 다음과 같다.

예를 들어, A[3]에는 4라는 값이 저장되어 있는데, 이는 S의 접미사를 사전순으로 정렬했을 때 세 번째에 위치하는 접미사가 시작 인덱스가 4인 `ana$`라는 의미이다.

접미사 배열을 만들면 빈 문자열이 항상 처음에 오게 됨을 알 수 있다. 즉, 빈 문자열으로부터 얻을 수 있는 정보가 없기 때문에 빈 문자열을 생략할 수 있다.

## 접미사 배열을 구현하는 알고리즘

### 나이브한 알고리즘

접미사 배열을 만드는 가장 쉬운 방법은 비교 정렬 알고리즘을 사용하는 것이다. 문자열의 길이를 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 알고리즘

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`를 첫 번째 문자에 대해 정렬한 뒤 첫 번째 랭크를 부여한 결과는 다음과 같다.

이때 j는 접미사 배열의 인덱스이고 i는 접미사가 시작되는 문자의 번호, 즉 접미사의 이름이다.

첫 번째 랭크는 접미사의 앞에서부터 2^0=1번째 자리까지를 비교한 정보이므로, 두 번째 자리를 비교한 정보를 이용하여 다음 랭크를 구할 수 있다.
그러나 모든 접미사에 대해 랭크가 부여되어 있으므로 두 번째 자리를 비교한 정보는 접미사 i+2^0의 랭크로 구할 수 있다. 이때 문자열이 끝나서 i+2^0 접미사가 없는 경우 모든 문자보다 앞서야 하므로 -1로 처리한다.
그러므로 i의 첫 번째 랭크와 접미사 i+2^0의 첫 번째 랭크를 기준으로 정렬한 뒤 두 번째 랭크를 부여할 수 있다.

두 번째 랭크 역시, i의 첫 번째 랭크와 i+2^0의 랭크가 이전 인덱스와 같으면 같은 랭크, 다르면 1을 더한 랭크로 부여한다.
첫 번째 랭크와 접미사 i+1의 랭크를 기준으로 구한 두 번째 랭크는 다음과 같다.

같은 방식으로 i와 i+2^1의 두 번째 랭크에 대해 정렬한 뒤 부여한 세 번째 랭크는 다음과 같다.

이와 같은 방식으로 비교 범위가 문자열의 길이 n보다 커질 때까지 반복하면 접미사 배열을 얻을 수 있다.

#### [[기수 정렬]]의 구체적인 방법
랭크의 크기는 최대 n이므로 두 번의 기수 정렬을 사용하여 시간 복잡도를 줄일 수 있다. 랭크가 구해진 상태에서 접미사 i+2^k의 랭크에 대해 기수 정렬을 하고 i의 랭크에 대해 한 번 더 기수 정렬을 하면 정렬을 \mathcal{O}(n)에 수행할 수 있다. Manber-Myers 알고리즘은 O(\lg{n})번의 단계를 거치므로, 기수 정렬을 사용하였을 때의 총 시간 복잡도는 \mathcal{O}(n\lg{n})이 된다.

### SA-IS 알고리즘

SA-IS 알고리즘은 다음 문자가 현재 문자보다 사전순으로 뒤인지 앞인지에 따라 문자열을 분류한 뒤, 여러 단계의 **추측**이라는 과정을 통해 접미사 배열을 구성한다.

## 응용

## 역사
접미사 배열은 원래 Gene Myers와 Udi Manber가 접미사 트리보다 메모리 소비를 줄이려고 개발하였다. 이 경향이 이어져 압축된 접미사 배열이나 압축 전문 인덱스 등이 개발되었다.

## 같이 보기
* 접미사 트리

## 참고 문헌
* Udi Manber and Gene Myers (1991). "Suffix arrays: a new method for on-line string searches". *SIAM Journal on Computing*, Volume 22, Issue 5 (October 1993), pp. 935–948.
* Pang Ko and Srinivas Aluru (2003). "Space efficient linear time construction of suffix arrays." In *Combinatorial Pattern Matching (CPM 03)*. LNCS 2676, Springer, 2003, pp 203–210.
* Juha Kärkkäinen and Peter Sanders (2003). "Simple linear work suffix array construction." In *Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP '03)*. LNCS 2719, Springer, 2003, pp. 943–955.
* Klaus-Bernd Schürmann and Jens Stoye (2005). "An incomplex algorithm for fast suffix array construction". In *Proceedings of the 7th Workshop on Algorithm Engineering and Experiments and the 2nd Workshop on Analytic Algorithmics and Combinatorics (ALENEX/ANALCO 2005)*, 2005, pp. 77–85.

## 외부 링크
* 버로우즈-휠러 변환(BWT)을 위한 접미사 정렬 모듈, C 언어 코드로 되어 있음
* 루비 프로그래밍 언어로 구현한 접미사 배열
* 접미사 배열 라이브러리와 툴

분류:배열
분류:자료 구조
분류:알고리즘
분류:문자열 자료 구조