접미사 배열

컴퓨터 과학에서 접미사 배열이란 어떤 문자열의 접미사를 사전식 순서대로 나열한 배열을 말한다. 문자열 검색이나 전문 검사 등에 쓰인다. 영어로는 인데, 이를 번역하지 않고 서픽스 배열이나 서픽스 어레이라고 부르기도 한다.
정의.
formula_1이라는 문자열이 있다고 하자. 이때 formula_2, formula_3, … formula_4은 문자열formula_5를 구성하는 문자이다. 그리고 formula_6는 formula_7번째 문자부터 formula_8번째 문자까지 formula_5의 부분 문자열이라고 하자.
문자열 formula_5에 대한 접미사배열 formula_11는 formula_5의 접미사들을 사전식 순서로 정렬했을 때 접미사의 시작 위치를 저장한 정수 배열이다. 즉, formula_13에 저장된 내용은 사전순으로 formula_7 번째인 formula_5의 접미사의 시작 위치이다. 달리 말하자면, 문자열 formula_5의 길이를 formula_17라고 할 때, formula_18인 formula_7에 대해 사전순으로 formula_20이다.
예시.
다음과 같이 인덱스가 정의된 문자열 formula_5 = codice_1가 있다고 하자.
문자열의 끝은 사전순으로 어떠한 문자보다 앞서기 때문에 codice_2라는 특수 문자로 표시한다. 이때 문자열 formula_5의 접미사들은 시작 인덱스를 formula_7라고 할 때 다음과 같이 나타낼 수 있다.
그리고 접미사들을 다음과 같이 오름차순으로 정렬할 수 있다.
이때 접미사 배열 formula_11는 위와 같이 정렬된 접미사의 시작 위치를 저장한 배열이다. formula_8를 접미사 배열 formula_11의 인덱스라고 할 때 formula_11는 다음과 같다.
formula_11의 각 원소에 대응되는 접미사를 가로로 나열하면 다음과 같다.
예를 들어, formula_29에는 4라는 값이 저장되어있는데, 이는 formula_5의 접미사를 사전순으로 정렬했을 때 세번째에 위치하는 접미사가 시작 인덱스가 4인 codice_3라는 의미이다.
접미사 배열을 만들면 빈 문자열이 항상 처음에 오게 됨을 알 수 있다. 즉, 빈 문자열으로부터 얻을 수 있는 정보가 없기 때문에 빈 문자열을 생략할 수 있다.
접미사 배열을 구현하는 알고리즘.
나이브한 알고리즘.
접미사 배열을 만드는 가장 쉬운 방법은 비교 정렬 알고리즘을 사용하는 것이다. 문자열의 길이를 formula_17라고 할 때 접미사는 formula_17개가 만들어지므로 정렬에 필요한 비교 횟수는 점근표기법으로 formula_33으로 나타낼 수 있다. 두 문자열을 사전순으로 정렬하는 가장 빠른 방법은 모든 문자에 대해 순서를 비교하는 것이므로 접미사의 최대 길이인 formula_34번의 비교를 통해 두 접미사를 비교할 수 있다.
접미사끼리 비교하는 횟수는 formula_35이고, 한 쌍의 접미사의 사전 순서를 판단하는데 필요한 비교 횟수는 formula_34이므로 총 시간 복잡도는 formula_37이 된다.
Manber-Myers 알고리즘.
Manber-Myers 알고리즘은 정렬할 때 랭크라는 개념과 기수 정렬을 사용하여 시간복잡도를 줄인 알고리즘이다. 이 알고리즘은 접미사 배열을 구하는 다양한 알고리즘 가운데 프로그래밍 대회에서 자주 사용되는데, 시간복잡도가 더 작은 알고리즘은 짧은 시간 안에 구현하기 어렵기 때문이다.
이 알고리즘은 여러 단계의 정렬을 통해 전체 접미사를 정렬한다. Manber-Myers 알고리즘을 다음과 같이 개략적으로 설명할 수 있다.
 1. 문자열 formula_5의 접미사들을 첫번째 글자와 두번째 글자에 대해 사전순으로 정렬한다.
 2. 정렬된 순서를 바탕으로 랭크를 부여한다.
 3. 접미사의 특성을 이용하여 부여된 두개의 랭크를 기준으로 정렬한다. (비교 범위가 두배가 된다.)
 4. 2로 돌아간다.
랭크.
랭크는 정렬을 위해 정한 일정한 기준으로, 어떤 접미사에서 접두사를 빼도 접미사인 성질을 응용한 것이다. Manber-Myers 알고리즘에서는 각 단계마다 접미사에 랭크를 부여하고, 랭크를 기준으로 정렬을 한다. formula_39번째 단계에서 사용되는 랭크는 접미사의 앞에서 formula_40 글자의 순서 정보를 담고 있다.
랭크를 기준으로 수행을 할 때마다 비교 범위는 두배가 되므로 접미사에 대해 formula_41단계를 거치게 된다. 그리고 각 단계마다 랭크를 부여하고 정렬하는 작업을 하는데, 랭크는 모든 원소를 순차적으로 확인하면서 구할 수 있으므로 시간복잡도는 formula_34이고, 비교기반정렬의 시간 복잡도는formula_33이므로 랭크를 기반으로 한 비교기반 정렬을 사용하면 총 시간복잡도는 formula_44이 된다.
첫번째 단계에서는 참조할 기존의 랭크가 없기 때문에 첫번째 랭크를 정하기 위한 사전 작업이 필요하다. 첫번째 랭크는 접미사의 앞에서부터 formula_45번째 글자의 정보를 가져야 하므로 첫번째 글자에 대해 사전순으로 정렬한 뒤 첫번째 랭크를 부여하면 된다. 랭크는 정렬된 순서에 따라 증가하는 어떠한 수여도 무관하지만, 일반적으로 다음과 같은 과정을 통해 연속된 자연수를 부여한다.
 1. 비교하는 범위에 해당하는 문자가 없으면 -1을 부여한다.
 2. 정렬된 배열에서 비교하는 범위에 대해 이전 인덱스(j-1)와 같으면 같은 랭크를, 다르면 1을 더한 랭크를 부여한다.
문자열 formula_5=codice_1를 첫번째 문자에 대해 정렬한 뒤 첫번째 랭크를 부여한 결과는 다음과 같다.
이때 j는 접미사 배열의 인덱스이고 i는 접미사가 시작되는 문자의 번호, 즉, 접미사의 이름이다.
첫번째 랭크는 접미사의 앞에서부터 formula_47번째 자리까지를 비교한 정보이므로, 두번째 자리를 비교한 정보를 이용하여 다음 랭크를 구할 수 있다.
그러나 모든 접미사에 대해 랭크가 부여되어있으므로 두번째 자리를 비교한 정보는 접미사 formula_48의 랭크로 구할 수 있다. 이때 접미사가 끝나서 formula_48 접미사가 없는 경우 모든 문자보다 앞서야 하므로 -1로 처리한다.
그러므로 formula_7의 첫번째 랭크와 접미사 formula_48의 첫번째 랭크를 기준으로 정렬한 뒤 두번째 랭크를 부여할 수 있다.
두번째 랭크 역시, formula_7의 첫번째 랭크와 formula_48의 랭크가 이전 인덱스와 같으면 같은 랭크, 다르면 1을 더한 랭크로 부여한다.
첫번째 랭크와 접미사 formula_54의 랭크를 기준으로 구한 두번째 랭크는 다음과 같다.
같은 방식으로 formula_7와 formula_56의 두번째 랭크에 대해 정렬한 뒤 부여한 세번째 랭크는 다음과 같다.
이와 같은 방식으로 비교 범위가 문자열의 길이 formula_17보다 커질 때까지 반복하면 접미사 배열을 얻을 수 있다.
기수 정렬의 구체적인 방법.
랭크의 크기는 최대 formula_17이므로 두번의 기수정렬을 사용하여 시간 복잡도를 줄일 수 있다. 랭크가 구해진 상태에서 접미사 formula_59의 랭크에 대해 기수정렬하고 formula_7의 랭크에 대해 기수정렬하면 정렬을 formula_61에 수행할 수 있다. Manber-Myers 알고리즘은 formula_62번의 단계를 거치므로, 기수정렬을 사용하였을 때의 총 시간 복잡도는 formula_63가 된다.
SA-IS 알고리즘.
SA-IS 알고리즘은 다음 문자가 현재 문자보다 사전순으로 뒤인지 앞인지에 따라 문자열을 분류한 뒤, 여러단계의 추측이라는 과정을 통해 접미사 배열을 구성한다.
역사.
접미사 배열은 원래 Gene Myers와 Udi Manber가 접미사 트리보다 메모리 소비를 줄이려고 개발하였다. 이 경향이 이어져 압축된 접미사 배열이나 압축 전문 인덱스 등이 개발되었다.