문자열 집합에 대한 일반화접미사트리의 병행적 생성 알고리즘 = A Concurrent Construction of the Generalized Suffix Tree for a Set of Strings

국문 초록 (Abstract)

접미사트리 는 주어진 한 문자열의 모든 접미사를 표현하는 트리로, 문자열 처리, 압축 등 다양한 분야에서 활용된다. 접미사트리는 문자열 집합에 대한 자료구조로 확장될 수 있는데, 이를 일반화접미사트리 라 부른다. 본 논문에서는 일반화접미사트리를 병행적 으로 생성하는 문제를 다룬다. 기존의 알고리즘은 문자열들을 역방향으로 처리하면서 일반화접미사트리를 생성하는데, 접미사트리가 활용되는 대부분의 응용에서는 문자열을 정방향으로 처리하고 있어, 기존의 알고리즘은 활용 범위가 매우 제한된다. 본 논문에서는 문자열들을 정방향으로 처리하면서 일반화접미사트리를 병행적으로 생성하는 알고리즘을 제시함으로써 기존 알고리즘의 문제점을 극복한다.

다국어 초록 (Multilingual Abstract)

The suffix tree, a compacted trie representing all suffixes of a given string, is utilized in various applications such as string processing and data compression. The suffix tree can be extended to a data structure of a set of strings, called the generalized suffix tree. In this paper we consider the problem of constructing concurrently the generalized suffix tree. The previous algorithm constructs the generalized suffix tree by processing strings in backward direction. In most applications, strings are handled in forward direction, and thus the previous algorithm has some limits. We propose an algorithm for constructing concurrently the generalized suffix tree by processing strings in forward direction.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 접미사트리
• 3. 병행 생성 알고리즘
• 4. 결론
• 참고문헌

참고문헌 (Reference)

• 1 J.C. Na, "Truncated suffix trees and their application to data compression" 304 (304): 87-101, 2003
• 2 나중채, "On-line construction of two-dimensional suffix trees in O(n(2) log n) time" SPRINGER 48 (48): 173-186, 200706
• 3 R. Giancarlo, "On-line construction of two-dimensional suffix trees" 15 (15): 72-127, 1999
• 4 E. Ukkonen, "On-line construction of suffix trees" 14 (14): 249-260, 1995
• 5 M. Farach-Colton, "On the Sorting-complexity of Suffix Tree Construction" 47 (47): 987-1011, 2000
• 6 P. Weiner, "Linear pattern matching algorithms" 1-11, 1973
• 7 M. Crochemore, "Jewels of Stringology" World Scientific Publishing, Singapore 2002
• 8 J. Ziv, "Compression of individual sequences via variable-rate coding" 24 (24): 530-536, 1978
• 9 D. Gusfield, "Algorithms on Strings, Trees, and Sequences" Cambridge Univ. Press 1997
• 10 J. Ziv, "A universal algorithm for sequential data compression" 23 (23): 337-343, 1977
• 11 E. M. McCreight, "A space-economical suffix tree construction algorithm" 23 (23): 262-272, 1976
• 12 R. Giancarlo, "A generalization of the suffix tree to square matrices, with application" 24 (24): 520-562, 1995