접미사 배열은 접미사 트리의 공간 소모량을 줄이기 위해 고안된 데이터 구조이다. 이 데이터 구조는 아리조나 대학의 Udi Manber 씨와 Gene Myers 씨에 의해서 1989년 5월에 제안되었다.
다음은 해당 논문의 연결이다.
이 데이터 구조는 기본적으로 다음과 같이 생성된다.
- 주어진 문자열에 대한 모든 접미사 문자열을 가장 긴 것부터 가장 짧은 것 까지 나열한다.
- 나열하는 과정에서 각 접미사 문자열을 순서대로 번호를 할당한다.
- 문자열을 사전식 순서의 오름차순으로(가나다) 정렬한다.
- 접미사 배열은 각 접미사 문자열에 할당된 번호만을 가진 배열이다.
예를 들어, banana를 정렬하여 보자.
숫자 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
문자[숫자] |
b | a |
n |
a |
n |
a |
$ |
문자열의 마지막은 사전식 순서에서 사용되는 문자 집합에서 가장 큰 값을 가진 문자를 이용한다. 이 문자열에 대한 접미사 문자열은 다음과 같다.
접미사 문자열 |
숫자 |
| banana$ | 0 |
anana$ |
1 |
| nana$ | 2 |
| ana$ | 3 |
na$ |
4 |
a$ |
5 |
| $ | 6 |
그리고 이 접미사 문자열들을 사전식 순서대로 정렬하면 다음과 같다.
접미사 문자열 |
숫자 |
| $ | 6 |
a$ |
5 |
| ana$ | 3 |
| anana$ | 1 |
| banana$ | 0 |
na$ |
4 |
nana$ |
2 |
접미사 배열은 정렬된 숫자를 배열화 하여 얻을 수 있다.
즉, A = (6, 5, 3, 1, 0, 4, 2)이다.
현재까지 개발된 Suffix Array 생성에 대한 알고리즘의 벤치 마크 결과는 다음을 참고하기 바란다.
댓글