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

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 : 시스템 및 이론 / 38권 / 5호 / 216 ~ 222페이지
· 저자명 : 조석현, 윤현철, 나중채, 심정섭

초록

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

영어초록

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.

참고자료

· 없음