접미사 배열

3. 알고리즘

접미사 트리는 $\backslash mathcal\{O\}(n)$ 시간에 구축할 수 있으며, 트리 깊이 우선 탐색을 통해 접미사 배열로 변환하는 데에도 $\backslash mathcal\{O\}(n)$ 시간이 걸리므로, 접미사 배열을 $\backslash mathcal\{O\}(n)$ 시간에 구축할 수 있는 알고리즘이 존재한다.

비교 기반 정렬 알고리즘을 사용하는 가장 단순한 방법은 $\backslash mathcal\{O\}(n\; \backslash log\; n)$번의 접미사 비교가 필요하지만, 접미사 비교는 $\backslash mathcal\{O\}(n)$ 시간에 실행되므로, 이 방식의 전체 실행 시간은 $\backslash mathcal\{O\}(n^2\; \backslash log\; n)$이다.

더 발전된 알고리즘들은 정렬될 접미사가 임의의 문자열이 아닌 서로 관련되어 있다는 사실을 활용한다. 이러한 알고리즘들은 최소 점근적 복잡도 $\backslash Theta(n)$, 공간 효율성, 실제 적용 시 빠른 속도를 목표로 한다.

== 나이브 알고리즘 ==

비교 기반 정렬 알고리즘을 사용하면 접미사 배열을 구축할 수 있다. 문자열의 길이를 $n$이라 할 때, 접미사는 $n$개가 만들어지므로 정렬에 필요한 비교 횟수는 $\backslash mathcal\{O\}(n\backslash lg\; n)$이다. 두 문자열을 사전순으로 정렬하는 가장 빠른 방법은 모든 문자에 대해 순서를 비교하는 것이므로, 접미사의 최대 길이인 $\backslash mathcal\{O\}(\{n\})$번의 비교를 통해 두 접미사를 비교할 수 있다.

접미사끼리 비교하는 횟수는 $\backslash mathcal\{O\}(n\; \backslash lg\; n)$이고, 한 쌍의 접미사의 사전 순서를 판단하는데 필요한 비교 횟수는 $\backslash mathcal\{O\}(\{n\})$이므로 총 시간 복잡도는 $\backslash mathcal\{O\}(\{n\}^\{2\}\; \backslash lg\; n)$이 된다.

== Manber-Myers 알고리즘 ==

랭크는 정렬을 위해 정한 일정한 기준으로, 어떤 접미사에서 접두사를 빼도 접미사인 성질을 응용한다. Manber-Myers 알고리즘에서는 각 단계마다 접미사에 랭크를 부여하고, 랭크를 기준으로 정렬을 한다. $k$번째 단계에서 사용되는 랭크는 접미사의 앞에서 $2^\{k-1\}$ 글자의 순서 정보를 담고 있다.

랭크를 기준으로 수행을 할 때마다 비교 범위는 두배가 되므로 접미사에 대해 $\backslash mathcal\{O\}(\backslash lg\; n)$단계를 거치게 된다. 그리고 각 단계마다 랭크를 부여하고 정렬하는 작업을 하는데, 랭크는 모든 원소를 순차적으로 확인하면서 구할 수 있으므로 시간복잡도는 $\backslash mathcal\{O\}(\{n\})$이고, 비교기반정렬의 시간 복잡도는$\backslash mathcal\{O\}(n\backslash lg\; n)$이므로 랭크를 기반으로 한 비교기반 정렬을 사용하면 총 시간복잡도는 $\backslash mathcal\{O\}(\backslash lg\{n\}(n+n\backslash lg\{n\}))\; =\; \backslash mathcal\{O\}(n\backslash 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$보다 커질 때까지 반복하면 접미사 배열을 얻을 수 있다.

== 랭크 ==

랭크는 정렬을 위해 정한 일정한 기준으로, 어떤 접미사에서 접두사를 빼도 접미사인 성질을 응용한다. Manber-Myers 알고리즘에서는 각 단계마다 접미사에 랭크를 부여하고, 랭크를 기준으로 정렬을 한다. $k$번째 단계에서 사용되는 랭크는 접미사의 앞에서 $2^\{k-1\}$ 글자의 순서 정보를 담고 있다.

랭크를 기준으로 수행을 할 때마다 비교 범위는 두배가 되므로 접미사에 대해 $\backslash mathcal\{O\}(\backslash lg\; n)$단계를 거치게 된다. 그리고 각 단계마다 랭크를 부여하고 정렬하는 작업을 하는데, 랭크는 모든 원소를 순차적으로 확인하면서 구할 수 있으므로 시간복잡도는 $\backslash mathcal\{O\}(\{n\})$이고, 비교기반정렬의 시간 복잡도는$\backslash mathcal\{O\}(n\backslash lg\; n)$이므로 랭크를 기반으로 한 비교기반 정렬을 사용하면 총 시간복잡도는 $\backslash mathcal\{O\}(\backslash lg\{n\}(n+n\backslash lg\{n\}))\; =\; \backslash mathcal\{O\}(n\backslash 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의 랭크에 대해 기수정렬하면 정렬을 O(n)에 수행할 수 있다. Manber-Myers 알고리즘은 O(lg n)번의 단계를 거치므로, 기수정렬을 사용하였을 때의 총 시간 복잡도는 O(n lg n)가 된다.

== SA-IS 알고리즘 ==

SA-IS 알고리즘은 다음 문자가 현재 문자보다 사전순으로 뒤인지 앞인지에 따라 문자열을 분류한 뒤, 여러 단계의 '''추측'''이라는 과정을 통해 접미사 배열을 구성한다.^[7] 이 알고리즘은 선형 시간 복잡도 $\backslash mathcal\{O\}(n)$을 가지며, 100행 정도의 C 언어 프로그램으로 구현할 수 있다.^[7] 2009년에 Ge Nong 등이 SA-IS 법을 발표했다.^[7]

접미사 트리는 $\backslash mathcal\{O\}(n)$ 시간에 구축할 수 있으며, 트리 깊이 우선 탐색을 통해 접미사 배열로 변환하는 데에도 $\backslash mathcal\{O\}(n)$ 시간이 걸리므로, 접미사 배열을 $\backslash mathcal\{O\}(n)$ 시간에 구축할 수 있는 알고리즘이 존재한다.

Yuta Mori가 논문 발표와 동시에 SA-IS 법의 구현을 공개했으며^[8], 논문에서도 언급되고 있다. SA-IS 알고리즘은 알려진 가장 빠른 접미사 배열 구축 알고리즘 중 하나이며, Yuta Mori가 신중하게 구현한 버전^[1]은 대부분의 다른 선형 또는 초선형 구축 방식을 능가한다.

== 기타 알고리즘 ==

접미사 트리는 $\backslash mathcal\{O\}(n)$ 시간에 구축될 수 있으며, 트리 깊이 우선 탐색을 통해 접미사 배열로 변환하는 데에도 $\backslash mathcal\{O\}(n)$ 시간이 걸린다. 따라서 접미사 배열을 $\backslash mathcal\{O\}(n)$ 시간에 구축할 수 있는 알고리즘이 존재한다.

접미사 배열을 구축하는 가장 단순한 방법은 비교 기반 정렬 알고리즘을 사용하는 것이다. 이러한 알고리즘은 $\backslash mathcal\{O\}(n\; \backslash log\; n)$번의 접미사 비교가 필요하지만, 접미사 비교는 $\backslash mathcal\{O\}(n)$ 시간에 실행되므로, 이 방식의 전체 실행 시간은 $\backslash mathcal\{O\}(n^2\; \backslash log\; n)$이다.

더 발전된 알고리즘들은 정렬될 접미사가 임의의 문자열이 아닌 서로 관련되어 있다는 사실을 활용한다. 이러한 알고리즘들은 최소 점근적 복잡도 $\backslash Theta(n)$, 공간 효율성, 실제 적용 시 빠른 속도를 목표로 한다.

이러한 목표를 달성하는 알고리즘 중 하나로, 의 SA-IS 알고리즘이 있다. 이 알고리즘은 비교적 간단하며, LCP 배열을 동시에 구축하도록 개선될 수 있다. SA-IS 알고리즘은 알려진 가장 빠른 접미사 배열 구축 알고리즘 중 하나이며, Yuta Mori가 신중하게 구현한 버전^[1]은 대부분의 다른 선형 또는 초선형 구축 방식을 능가한다.

접미사 배열 구축 알고리즘은 시간 및 공간 요구 사항 외에도 지원하는 알파벳에 따라 구분된다. 즉, 알파벳 크기가 상수로 제한되는 ''고정 알파벳'', 문자가 $n$에 따라 달라지는 범위의 정수인 ''정수 알파벳'', 그리고 문자 비교만 허용되는 ''일반 알파벳''이 있다.

대부분의 접미사 배열 구축 알고리즘은 접두사 배가, 재귀적, 유도 복사 방식 중 하나를 기반으로 한다. 정수 알파벳에 대한 잘 알려진 재귀적 알고리즘은 의 ''DC3 / skew'' 알고리즘이다. 이 알고리즘은 선형 시간 내에 실행되며, 병렬 및 외부 메모리 접미사 배열 구축 알고리즘의 기반으로 성공적으로 사용되었다. 유도 복사 알고리즘은 이미 정렬된 하위 집합을 사용하여 나머지 접미사를 빠르게 정렬하도록 유도한다는 점에서 재귀적 알고리즘과 유사하며, 차이점은 이 알고리즘들이 재귀보다 반복을 선호하여 선택된 접미사 하위 집합을 정렬한다는 것이다.

실용적인 오픈 소스 작업에서, 접미사 배열 구축에 일반적으로 사용되는 루틴은 1999년 Larsson-Sadakane 알고리즘을 기반으로 한 qsufsort였다.^[2] 이 루틴은 2017년 현재 "주 메모리에서 가장 빠른 알려진 접미사 정렬 알고리즘"인 Yuta Mori의 DivSufSort로 대체되었다. 이 역시 LCP 배열을 계산하도록 수정될 수 있다. 이는 Itoh-Tanaka와 결합된 유도 복사를 사용한다.^[3] 2021년에는 Ilya Grebnov가 이 알고리즘을 더 빠르게 구현하여^[4] 평균적으로 Silesia Corpus에서 DivSufSort 구현보다 65%의 성능 향상을 보였다.^[5]

3. 1. 나이브 알고리즘

3. 2. Manber-Myers 알고리즘

이때 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$보다 커질 때까지 반복하면 접미사 배열을 얻을 수 있다.

3. 2. 1. 랭크

이때 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$보다 커질 때까지 반복하면 접미사 배열을 얻을 수 있다.

3. 2. 2. 기수 정렬의 구체적인 방법

3. 3. SA-IS 알고리즘

3. 4. 기타 알고리즘

4. 응용

접미사 배열은 문자열 S 내에서 하위 문자열 패턴 P의 모든 발생 위치를 빠르게 찾기 위한 색인으로 사용될 수 있다. 패턴의 모든 발생 위치를 찾는 것은 해당 하위 문자열로 시작하는 모든 접미사를 찾는 것과 같다. 사전식 순서 덕분에 이러한 접미사는 접미사 배열에서 함께 그룹화되며 이진 검색을 사용하여 효율적으로 찾을 수 있다. 첫 번째 검색은 간격의 시작 위치를 찾고, 두 번째 검색은 종료 위치를 결정한다.

길이 $n$의 문자열 $S$에서 길이 $m$의 하위 문자열 패턴 $P$를 찾는 데는 단일 접미사 비교에 $m$개의 문자를 비교해야 하므로 $\backslash mathcal\{O\}(m\; \backslash log\; n)$ 시간이 걸린다. LCP 정보를 사용하면 이 경계를 $\backslash mathcal\{O\}(m\; +\; \backslash log\; n)$ 시간으로 개선할 수 있다. 즉, 패턴 비교가 패턴과 현재 검색 간격의 최장 공통 접두사의 일부라는 것이 이미 알려져 있을 때 특정 문자를 다시 비교할 필요가 없다.

접미사 배열을 사용하면 검색 대상 문자열의 출현 위치를 고속으로 검색할 수 있다. 접미사 배열은 사전순으로 정렬되어 있으므로, 검색 대상이 되는 문자열의 검색에는 고속 이진 탐색 알고리즘을 이용할 수 있다. $m$을 검색 문자열의 길이라고 하면, 단순한 구현에서는 이진 탐색으로 $O(m\; \backslash log\; n)$의 계산 시간이 걸린다.

바로 앞 접미사와, 접미사의 선두에서 몇 문자가 공통되는 문자가 있는 경우, 그 최대 문자 수를 최장 공통 접두사(LCP, Longest Common Prefix)라고 부르는데, 미리 구해둔 LCP를 통해 불필요한 비교를 생략하여 검색을 고속화할 수 있다. 이때, $O(m\; +\; \backslash log\; n)$의 시간으로 검색할 수 있다.

Burrows–Wheeler 변환(BWT)은 문자열의 모든 순환 순열을 정렬해야 한다. 이 문자열이 다른 모든 문자보다 사전적으로 작은 특수 문자(즉, $)로 끝나면 정렬된 회전된 BWT 행렬의 순서는 접미사 배열의 접미사 순서에 해당한다. 따라서 BWT는 텍스트의 접미사 배열을 먼저 구성한 다음 BWT 문자열을 추론하여 선형 시간으로 계산할 수 있다. $BWT[i]\; =\; S[A[i]-1]$.

접미사 배열을 사용하여 BWT를 선형 시간에 계산할 수 있으며, BWT는 데이터 압축에 활용된다.

접미사 배열은 문자열 내에서 하위 문자열 패턴의 모든 발생 위치를 빠르게 찾기 위한 색인으로 사용될 수 있다. 패턴의 모든 발생 위치를 찾는 것은 하위 문자열로 시작하는 모든 접미사를 찾는 것과 같다. 사전식 순서 덕분에 이러한 접미사는 접미사 배열에서 함께 그룹화되며 두 개의 이진 검색을 사용하여 효율적으로 찾을 수 있다. 첫 번째 검색은 간격의 시작 위치를 찾고, 두 번째 검색은 종료 위치를 결정한다.

길이 $n$의 문자열 $S$에서 길이 $m$의 하위 문자열 패턴 $P$를 찾는 데는 단일 접미사 비교에 $m$개의 문자를 비교해야 하므로 $\backslash mathcal\{O\}(m\; \backslash log\; n)$ 시간이 걸린다. 맨버/Manber^영어와 마이어스/Myers^영어는 LCP 정보를 사용하여 이 경계를 $\backslash mathcal\{O\}(m\; +\; \backslash log\; n)$ 시간으로 개선하는 방법을 설명한다. 아이디어는 패턴 비교가 패턴과 현재 검색 간격의 최장 공통 접두사의 일부라는 것이 이미 알려져 있을 때 특정 문자를 다시 비교할 필요가 없다는 것이다. 아불엘호다/Abouelhoda^영어, 커츠/Kurtz^영어, 올레부쉬/Ohlebusch^영어는 경계를 더욱 개선하여 접미사 트리에서 알려진 것처럼 상수 알파벳 크기에 대해 $\backslash mathcal\{O\}(m)$의 검색 시간을 달성한다.

접미사 정렬 알고리즘은 Burrows–Wheeler 변환(BWT)을 계산하는 데 사용될 수 있다. BWT는 문자열의 모든 순환 순열을 정렬해야 한다. 이 문자열이 다른 모든 문자보다 사전적으로 작은 특수 문자(즉, $)로 끝나면 정렬된 회전된 BWT 행렬의 순서는 접미사 배열의 접미사 순서에 해당한다. 따라서 BWT는 텍스트의 접미사 배열을 먼저 구성한 다음 BWT 문자열을 추론하여 선형 시간으로 계산할 수 있다. $BWT[i]\; =\; S[A[i]-1]$.

접미사 배열은 또한 예제 기반 기계 번역에서 하위 문자열을 찾는 데 사용될 수 있으며, 통계적 기계 번역에서 사용되는 전체 구문 테이블보다 훨씬 적은 저장 공간을 요구한다.

접미사 배열의 많은 추가 응용 프로그램에는 LCP 배열이 필요하다.

접미사 배열은 문자열 S 내에서 하위 문자열 패턴 P의 모든 발생 위치를 빠르게 찾기 위한 색인으로 사용될 수 있다. 패턴의 모든 발생 위치를 찾는 것은 하위 문자열로 시작하는 모든 접미사를 찾는 것과 같다. 사전식 순서 덕분에 이러한 접미사는 접미사 배열에서 함께 그룹화되며 두 개의 이진 검색을 사용하여 효율적으로 찾을 수 있다. 첫 번째 검색은 간격의 시작 위치를 찾고, 두 번째 검색은 종료 위치를 결정한다.

길이 $n$의 문자열 $S$에서 길이 $m$의 하위 문자열 패턴 $P$를 찾는 데는 단일 접미사 비교에 $m$개의 문자를 비교해야 하므로 $\backslash mathcal\{O\}(m\; \backslash log\; n)$ 시간이 걸린다. LCP 정보를 사용하면 이 경계를 $\backslash mathcal\{O\}(m\; +\; \backslash log\; n)$ 시간으로 개선할 수 있다. 아이디어는 패턴 비교가 패턴과 현재 검색 간격의 최장 공통 접두사의 일부라는 것이 이미 알려져 있을 때 특정 문자를 다시 비교할 필요가 없다는 것이다. 상수 알파벳 크기에 대해 $\backslash mathcal\{O\}(m)$의 검색 시간을 달성하여 접미사 트리에서 알려진것과 같이 경계를 개선할수 있다.

접미사 정렬 알고리즘은 Burrows–Wheeler 변환(BWT)을 계산하는 데 사용될 수 있다. BWT는 문자열의 모든 순환 순열을 정렬해야 한다. 이 문자열이 다른 모든 문자보다 사전적으로 작은 특수 문자(즉, $)로 끝나면 정렬된 회전된 BWT 행렬의 순서는 접미사 배열의 접미사 순서에 해당한다. 따라서 BWT는 텍스트의 접미사 배열을 먼저 구성한 다음 BWT 문자열을 추론하여 선형 시간으로 계산할 수 있다. $BWT[i]\; =\; S[A[i]-1]$.

접미사 배열은 예제 기반 기계 번역에서 하위 문자열을 찾는 데 사용될 수 있으며, 통계적 기계 번역에서 사용되는 전체 구문 테이블보다 훨씬 적은 저장 공간을 요구한다.

접미사 배열은 최장 공통 부분 문자열(Longest Common Substring), 최장 반복 부분 문자열(Longest Repeated Substring) 문제 등 다양한 문자열 알고리즘에 응용될 수 있으며, LCP(Longest Common Prefix) 배열과 함께 사용하면 더욱 효율적인 문자열 처리가 가능하다.

4. 1. 문자열 검색

4. 2. Burrows-Wheeler 변환 (BWT)

4. 3. 생물 정보학

4. 4. 기타

5. 역사

진 마이어스(Gene Myers)와 우디 맘버(Udi Manber)가 접미사 트리의 공간 효율성을 개선하기 위해 1990년에 도입하였다. 이후 압축 접미사 배열, FM-index 등 관련 연구가 활발히 진행되었다. 2000년대에는 압축 전체 텍스트 인덱스인 압축 접미사 배열과 FM-Index가 등장했다.

6. 확장

6. 1. 일반화된 접미사 배열(Generalized Suffix Array)

6. 2. 향상된 접미사 배열(Enhanced Suffix Array)

• pos 배열 (pos[1,...n]): 모든 S 접미사의 정렬된 목록을 나타낸다. 접미사 대신 초기 위치만 저장하여 공간 복잡성을 줄인다.
• lcp 배열 (lcp[1,...n]): pos 배열에 저장된 연속적인 두 접미사의 최장 공통 접두사(Longest Common Prefix)의 길이를 저장한다.

• up[i]: 인덱스 `i-1`에서 끝나는 가장 긴 lcp-두 번째 간격의 자식 간격의 시작 인덱스를 기록한다.
• down[i]: 인덱스 `i`에서 시작하는 가장 긴 lcp-간격의 두 번째 자식 간격의 초기 인덱스를 저장한다.
• nextlIndex[i]: 해당 간격이 부모의 첫 번째 자식도 최종 자식도 아닌 경우에만 인덱스 `i`에서 시작하는 가장 긴 lcp-간격의 다음 형제 간격의 첫 번째 인덱스를 포함한다.

7. 구현 (한국어)

C++에서는 libdivsufsort^[9], Python에서는 pydivsufsort^[10] 등의 라이브러리를 사용할 수 있다. 야마시타 타츠오의 "SUFARY"(최종 업데이트 2002년)와 namazu의 저자인 타카바야시 사토시의 "Sary"(최종 업데이트 2005년)는 접미사 배열을 이용한 문자열 검색 소프트웨어이다.^[9][10]

7. 1. 라이브러리

8. 같이 보기

• 접미사 트리
• LCP 배열
• Burrows-Wheeler 변환
• 데이터 구조
• 배열
• 트리
• 트라이
• 기수 트리

참조

_[1] 웹사이트 sais https://sites.google[...] 2023-08-31
_[2] 학술지 Faster suffix sorting 2007-11-22
_[3] 학술지 Dismantling DivSufSort 2017-10-05
_[4] 웹사이트 New saca and bwt library (libsais) https://encode.su/th[...] 2021-10-03
_[5] Citation libsais https://github.com/I[...] 2021-09-22
_[6] 컨퍼런스 Suffix arrays: a new method for on-line string searches http://dl.acm.org/ci[...]
_[7] 컨퍼런스 Linear Suffix Array Construction by Almost Pure Induced-Sorting
_[8] 웹사이트 sais https://sites.google[...]
_[9] 웹사이트 SUFARY 臨時復旧ページ http://nais.to/~yto/[...]
_[10] 웹사이트 sary: Suffix Arrayのライブラリとツール http://sary.sourcefo[...]