일반화접미사배열을 이용한 선형시간 최장공통비상위문자열 알고리즘 = A Linear-time Algorithm for the Longest Common Nonsuperstring Problem Using Generalized Suffix Arrays

국문 초록 (Abstract)

상수크기의 알파벳 Σ에 대해 정의된 문자열 집합 F가 주어질 때, 주어진 문자열 집합 F 내의 어떤 문자열도 포함하지 않는 문자열을 F에 대한 공통비상위문자열이라 하고 공통비상위문자열 중에서 가장 긴 유한길이의 문자열을 최장공통비상위문자열이라 한다. 접미사 그래프 모델 또는 접두사 그래프 모델을 이용하여 F 내의 모든 문자열들의 길이의 합에 대해 선형시간에 최장공통비상위문자열을 찾는 알고리즘들이 최근 제시되었다. 이중 접미사 그래프 모델을 이용하는 알고리즘은 일반화접미사트리를 이용한다. 본 논문에서는 일반화접미사배열을 이용하여 접미사 그래프 모델을 생성함으로써 최장공통비상위문자열을 찾는 새로운 알고리즘을 제시한다. 또한, 기존의 두 알고리즘들과 새로이 제시된 알고리즘을 구현하여 성능을 실험한 결과를 제시한다.

다국어 초록 (Multilingual Abstract)

Given a set F of strings over constant size alphabet Σ, the common nonsuperstring of F is a string that is not a superstring of any string in F. Among the common nonsuperstrings of F, the longest one with finite length is the longest common nonsuperstring of F. Recently, two O(？？F？？)-time algorithms for finding the longest common nonsuperstring were proposed where ？？F？？denotes the sum of the lengths of the strings in F. One algorithm was based on the suffix graph model and the other was based on the prefix graph model. Especially, the former algorithm used generalized suffix trees to construct the suffix graph model. In this paper, we propose another linear-time algorithm based on suffix graph model. Our algorithm uses generalized suffix arrays to construct the suffix graph model. Also, we propose some experimental results to show the performance of our algorithm.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련 연구
• 3. T_s 생성알고리즘
• 4. 실험 결과 및 분석
• 5. 결론
• 참고문헌

참고문헌 (Reference)

• 1 최시원, "최장공통비상위문자열을 찾는 새로운 알고리즘" 한국정보과학회 15 (15): 67-71, 2009
• 2 P. A. Pevzner, "Towards DNA Sequencing Chips" MFCS 143-158, 1994
• 3 D. Maier, "The complexity of some problems on subsequences and supersequences" 322-336, 1978
• 4 A. R. Rubinov, "String noninclusion optimization problems" 11 (11): 456-467, 1998
• 5 P. Ko, "Space efficient linear time construction of suffix arrays" 203-210, 2003
• 6 J. Karkkainen, "Simple linear work suffix array construction" 943-955, 2003
• 7 T. Jiang, "Shortest consistent superstrings computable in polynomial time" 113-122, 1995
• 8 R. Drmanac, "Sequencing by hybridization (SBH) with oligonucleotide probes as an integral approach for the analysis of complex genomes" 59-79, 1992
• 9 D. K. Kim, "Linear-time construction of suffix arrays" 186-199, 2003
• 10 T. Kasai, "Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications" 181-192, 2001
• 11 J.C. Na, "Finding the longest common nonsuperstring in linear time" ELSEVIER SCIENCE BV 109 (109): 1066-1070, 200908
• 12 A. V. Aho, "Efficient string matching: an aid to bibliographic search" 333-340, 1975
• 13 J. Store, "Data compression via textual substitution" 928-961, 1982
• 14 J. Storer, "Data Compression: Methods and Theory" Computer Science Press 1988
• 15 M.R. Garey, "Computers and Intractobility" W.H. Freeman and Company 1979
• 16 V. G. Timkovsky, "Complexity of common subsequence and supersequence problems and related problems" 25 (25): 565-580, 1990
• 17 D. Gusfield, "Algorithms on Strings, Trees, and Sequences" Cambridge Univ. Press 1997
• 18 F. Kerschbaum, "A new way to think about secure, in: Computation: Language-based Secure Computation" 33-42, 2007