정수 문자집합상의 접미사트리 구축을 위한 새로운 합병알고리즘 = A New Merging Algorithm for Constructing Suffix Trees for Integer Alphabets

다국어 초록 (Multilingual Abstract)

A new approach of constructing a suffix tree T s for the given string S is to construct recursively a suffix tree T o for odd positions, construct a suffix tree T e for even positions from T o, and then merge T o and T e into T s . To construct suffix trees for integer alphabets in linear time had been a major open problem on index data structures. Farach used this approach and gave the first linear-time algorithm for integer alphabets. The hardest part of Farach's algorithm is the merging step. In this paper we present a new and simpler merging algorithm based on a coupled BFS (breadth-first search). Our merging algorithm is more intuitive than Farach's coupled DFS (depth-first search) merging, and thus it can be easily extended to other applications.

국문 초록 (Abstract)

주어진 스트링 S 의 접미사트리 T s 를 구축하기 위하여, 먼저 홀수위치들에 대한 접미사트리 T o 를 재귀적으로 구축하고, 짝수위치들에 대한 접미사트리 T e 를 T o 로 부터 구축한 다음, 와를 합병하여를 구축하는 새로운 방식이 사용되고 있다. 인덱스 자료구조에 관련된 문제들 중 정수 문자집합상의 접미사트리를 선형시간에 구축하는 문제는 오랫동안 미해결문제로 남아있었다. Farach은 이 방식을 적용하여 처음으로 선형시간이 소요되는 알고리즘을 제시하였다. 이 알고리즘 중 가장 어려운 곳은 합병하는 부분이다. 본 논문에서는 BFS(breadth-first search)에 기반한 새로운 합병알고리즘을 제안한다. 제안된 합병알고리즘은 Farach의 DFS(depth-first search) 방식보다 개념적으로 단순하게 동작하므로, 다른 응용으로 쉽게 확장될 수 있다.