접미사 배열

접미사 배열
유형	배열
고안자	Manber & Myers (1990)
빅 오 표기법에 따른 시간 복잡도
	평균	최악
공간	${\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가 있다고 하자.

i	1	2	3	4	5	6	7
$S[i]$	b	a	n	a	n	a	$

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

접미사	$i$
banana$	1
anana$	2
nana$	3
ana$	4
na$	5
a$	6
$	7

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

접미사	$i$
$	7
a$	6
ana$	4
anana$	2
banana$	1
na$	5
nana$	3

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

$j$	1	2	3	4	5	6	7
$A[j]$	7	6	4	2	1	5	3

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

$j$	$A[j]$	해당하는 접미사
1	7	$
2	6	a$
3	4	ana$
4	2	anana$
5	1	banana$
6	5	na$
7	3	nana$

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

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

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

나이브한 알고리즘

시간 복잡도	${\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 알고리즘

시간 복잡도	${\mathcal {O}}({n}\lg {n})$
공간 복잡도	${\mathcal {O}}(n)$

Manber-Myers 알고리즘은 정렬할 때 랭크라는 개념과 기수 정렬을 사용하여 시간 복잡도를 줄인 알고리즘이다. 이 알고리즘은 접미사 배열을 구하는 다양한 알고리즘 가운데 프로그래밍 대회에서 자주 사용되는데, 시간 복잡도가 더 작은 알고리즘은 짧은 시간 안에 구현하기 어렵기 때문이다.

이 알고리즘은 여러 단계의 정렬을 통해 전체 접미사를 정렬한다. Manber-Myers 알고리즘을 다음과 같이 개략적으로 설명할 수 있다.

1. 문자열 $S$의 접미사들을 첫 번째 글자와 두 번째 글자에 대해 사전순으로 정렬한다.
2. 정렬된 순서를 바탕으로 랭크를 부여한다.
3. 접미사의 특성을 이용하여 부여된 두 개의 랭크를 기준으로 정렬한다. (비교 범위가 두 배가 된다.)
4. 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. 비교하는 범위에 해당하는 문자가 없으면 -1을 부여한다.
2. 정렬된 배열에서 비교하는 범위에 대해 이전 인덱스($j-1$)와 같으면 같은 랭크를, 다르면 1을 더한 랭크를 부여한다.

문자열 $S$ = banana를 첫 번째 문자에 대해 정렬한 뒤 첫 번째 랭크를 부여한 결과는 다음과 같다.

$j$	접미사	$i$	첫 번째 글자	첫 번째 랭크
0	$	7	$	-1
1	a$	6	a	0
2	ana$	4	a	0
3	anana$	2	a	0
4	banana$	1	b	1
5	na$	5	n	2
6	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$의 랭크를 기준으로 구한 두 번째 랭크는 다음과 같다.

$j$	접미사	$i$	$i$의 첫 번째 랭크	$i+2^{0}$의 첫 번째 랭크	두 번째 랭크
0	$	7	-1	-1	-1
1	a$	6	0	-1	0
2	ana$	4	0	2	1
3	anana$	2	0	2	1
4	banana$	1	1	0	2
5	na$	5	2	0	3
6	nana$	3	2	0	3

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

$j$	접미사	$i$	$i$의 두 번째 랭크	$i+2^{1}$의 두 번째 랭크	세 번째 랭크
0	$	7	-1	-1	-1
1	a$	6	0	-1	0
2	ana$	4	1	0	1
3	anana$	2	1	1	2
4	banana$	1	2	3	3
5	na$	5	3	-1	4
6	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 알고리즘

시간 복잡도	${\mathcal {O}}(n)$
공간 복잡도	${\mathcal {O}}(n)$

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 언어 코드로 되어 있음
• 루비 프로그래밍 언어로 구현한 접미사 배열
• 접미사 배열 라이브러리와 툴