접미사 배열

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

접미사 배열이란 전산학에서 어떤 문자열접미사사전식 순서대로 나열한 배열을 말한다. 문자열 검색이나 전문 검사 등에 쓰인다. 영어로는 suffix array인데, 이를 번역하지 않고 서픽스 배열이나 서픽스 어레이라고 부르기도 한다.

개요[편집]

길이가 11인 문자열 "abracadabra"를 고려해 보자. 여기에는 "abracadabra", "bracadabra", "racadabra"하는 식으로 "a"까지 접미사가 11개 있다. 접미사들을 사전 순서대로 늘어놓으면 다음과 같다.

a
abra
abracadabra
acadabra
adabra
bra
bracadabra
cadabra
dabra
ra
racadabra

원래의 문자열이 이용 가능하면, 접미사들을 첫째 문자의 인덱스에 따라 완전하게 구별할 수 있다. 이 인덱스들을 사전 순서대로 나열하면 접미사 배열이 된다. 문자열 "abracadabra"에 대한 접미사 배열은 {11,8,1,4,6,9,2,5,7,10,3}이 된다. 접미사 "a"는 11번째 문자에서 시작하고 "abra"는 8번째 문자에서 시작하는 식이다. 나머지도 마찬가지로 확인할 수 있다.

빈 문자열을 "abracadabra"의 열두 번째 접미사로 간주할 수도 있다. 그러나 빈 문자열은 사전 순서상 언제나 다른 모든 접미사의 앞에 오기 때문에 특별한 정보가 없어서, 빈 문자열을 생략하더라도 아무런 문제가 없다.

알고리즘[편집]

접미사 배열을 만드는 가장 쉬운 방법은 효율적인 비교 정렬 알고리즘을 사용하는 것이다. 이에는 접미사 비교가 O(n \log n)만큼 필요한데, 접미사 비교가 O(n)시간 걸리기 때문에, 전체 수행 시간은 O(n^2 \log n)이 된다. 부분 정렬의 결과를 이용하여 불필요한 비교를 피하는 더욱 복잡한 알고리즘을 쓰면 성능이 O(n \log n)으로 향상된다. Pang Ko와 Srinivas AluruJuha, Petuha Kärkkäinen와 Peter Sanders 등 몇몇 \Theta(n) 알고리즘도 개발되었다. 이 방법들은 배열을 더욱 빠르게 구성하고 공간도 O(n)만 사용한다.

응용[편집]

역사[편집]

접미사 배열은 원래 Gene MyersUdi 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.

바깥 연결[편집]