효율적인 써픽스 배열 합병 알고리즘과 응용 = Efficient Merging Algorithms for Suffix Arrays and their Application

국문 초록 (Abstract)

대표적인 인덱스 자료 구조인 써픽스 트리와 써픽스 배열은 긴 문자열에서 임의의 패턴을 검색하는 데 효율적이다. 써픽스 트리는 써픽스 배열보다 큰 공간을 차지하지만, 이미 구축된 써픽스 트리의 정보를 이용하여 쉽게 합병할 수 있다. 본 논문에서는 문자열 A와 B에 대한 써픽스 배열이 구축되어 있을 때, A#B$의 일반화된 써픽스 배열을 구축하기 위한 합병 알고리즘을 두 가지 제시하였다. 이 알고리즘을 사용하면 기존의 유전체 서열 써픽스 배열을 재사용하는 방식으로 합병하여, 빠른 시간 안에 효율적으로 합병된 써픽스 배열을 만들 수 있다. 실험 결과, 합병 알고리즘은 일반화된 써픽스 배열을 다시 구축하는 것 보다 5배 정도 빠른 속도를 보였다.

목차 (Table of Contents)

• 요약
• 1. 서론
• 2. 개요
• 3. 합병 알고리즘
• 4. 응용 및 실험
• 5. 결론
• 참고문헌