접미사 배열: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 →랭크: 수식 수정 |
잔글 →랭크: 수식 수정 |
||
161번째 줄:
랭크는 정렬을 위해 정한 일정한 기준으로, 어떤 접미사에서 접두사를 빼도 접미사인 성질을 응용한 것이다. Manber-Myers 알고리즘에서는 랭크를 구하는 사전작업을 수행하는데, 각 단계마다 접미사는 랭크를 부여받고, 부여받은 랭크를 기준으로 정렬을 하게 된다. <math>k</math>번째 단계에서 사용되는 랭크 <math>rank[k]</math>는 접미사들의 앞에서 <math>2^{k-1}</math> 글자의 순서 정보를 담고 있다.
랭크를 기준으로 수행을 할 때마다 비교 범위는 두배가 되므로 접미사에 대해 <math>\mathcal{O}(\lg n)</math>단계를 거치게 된다. 그리고 각 단계마다 랭크<math>rank[k]</math>를 부여하고 부여된 랭크를 기준으로 정렬하는 작업을 한다. 랭크는 모든 원소를 순차적으로 확인하면서 구할 수 있으므로 시간복잡도는 <math>\mathcal{O}({n})</math>이다. 또한 비교기반정렬의 시간 복잡도는<math>\mathcal{O}(n\lg n)</math>이므로 랭크를 기반으로 한 비교기반 정렬을 사용하면 총 시간복잡도는 <math>\mathcal{O}(\lg{n}(n+n\lg{n})) = \mathcal{O}(n\lg^2{n})</math>이 된다.
랭크 기반 정렬을 수행하기 전에 우선 문자열<math>S</math>의 접미사들을 첫번째 자리와 두번째 자리에 대해 사전순으로 정렬해준다. 이때 해당하는 자리에 문자가 없으면 모든 문자보다 앞서도록 처리한다. 작업을 수행하고 나면 앞의 두 자리에 대해 정렬되어있게 된다. '''모든''' 접미사 <math>S[i,n]</math>에 대해 앞의 두 자리에 대해 정렬이 되어있으므로 또다른 접미사인<math>S[i+2,n]</math>에 대한 순서도 알 수 있다. 이 순서를 다음 랭크로 정하고 이전의 두 자를 비교한 정보를 더하면 접미사들을 네 글자까지 정렬한 결과를 알 수 있다. 이때 첫번째, 두번째 글자에 대한 정보는 필요없고 정렬된 순서만 필요하므로 두개의 숫자를 압축할 수 있다.
| |||