기관회원 [로그인]
소속기관에서 받은 아이디, 비밀번호를 입력해 주세요.
개인회원 [로그인]

비회원 구매시 입력하신 핸드폰번호를 입력해 주세요.
본인 인증 후 구매내역을 확인하실 수 있습니다.

회원가입
서지반출
Efficient Construction of Generalized Suffix Arrays by Merging Suffix Arrays
[STEP1]서지반출 형식 선택
파일형식
@
서지도구
SNS
기타
[STEP2]서지반출 정보 선택
  • 제목
  • URL
돌아가기
확인
취소
  • Efficient Construction of Generalized Suffix Arrays by Merging Suffix Arrays
  • Efficient Construction of Generalized Suffix Arrays by Merging Suffix Arrays
저자명
전정은,박희진,김동규,Jeon. Jeong-Eun,Park. Heejin,Kim. Dong-Kyue
간행물명
정보과학회논문지. Journal of KIISE. 시스템 및 이론
권/호정보
2005년|32권 6호|pp.268-278 (11 pages)
발행정보
한국정보과학회
파일정보
정기간행물|ENG|
PDF텍스트
주제분야
기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
서지반출

영문초록

본 논문에서는 A와 B의 써픽스 배열이 주어졌을 때 두 배열을 합병하여 이들의 일반화된 써픽스 배열을 구축하는 방법을 연구하였다. 흘수 써픽스와 짝수 써픽스같이 특별한 경우의 두 써픽스를 합병하는 알고리즘은 이미 발표되었지만, A와 』가 임의의 문자열인 일반적인 경우 두 써픽스 배열을 합병하는 효율적인 알고리즘은 아직 개발되지 않았다. 따라서 현재까지는 A와 B의 써픽스 배열을 합병하기 위해서 A와 B의 써픽스 배열이 이미 주어져 있음에도 불구하고 A$#$B$$$라는 문자열에 대한 써픽스 배열을 다시 구축해야했다. 본 논문에서는 상수 문자집합이나 정수 문자집합에서 정의된 임의의 두 문자열 A와 B에 대한 써픽스 배열을 합병하는 효율적인 알고리즘을 제시한다. 실험결과 상수문자집합의 경우 A$#$B$$$에대한 써픽스 배열을 다시 구축하는 것보다 합병하는 것이 5배 정도 빨랐다. 여기서 제시한 알고리즘은 써픽스 배열 A에서 스트링 B의 모든 써픽스를 검색하여야 한다. 이를 위해 써픽스 배열에서 정의한 써픽스 링크를 사용하였고, 또 써픽스 링크를 계산하는 효율적인 알고리즘도 개발하였다. 써픽스 링크는 생물정보학에서 사용되는 매칭 통계나 최장 공통 부분 문자열 검색처럼 다른 스트링의 써픽스 배열에서 주어진 스트링의 모든 써픽스를 찾는 데 이용할 수 있으므로, 이를 계산하는 효율적인 방법을 제시한 것 역시 많은 의미를 가진다. 실험을 통해 여기서 제시한 방법이 기존 알고리즘 중 가장 빠른 방법보다 3$~$4배 정도 빠르다는 것을 보였다.

기타언어초록

We consider constructing the generalized suffix way of strings A and B when the suffix arrays of A and B are given, j.e., merging two suffix arrays of A and B. There are efficient algorithms to merge some special suffix arrays such as the odd array and the even array. However, for the general case that A and B are arbitrary strings, no efficient merging algorithms have been developed. Thus, one had to construct the generalized suffix arrays of A and B by constructing the suffix array of A$#$B$$$ from scratch, even though the suffix ways of A and B are given. In this paper, we Present efficient merging algorithms for the suffix arrays of two arbitrary strings A and B drawn from constant and integer alphabets. The experimental results show that merging two suffix ways of A and B are about 5 times faster than constructing the suffix way of A$#$B$$$ from scratch for constant alphabets. Our algorithms include searching all suffixes of string B in the suffix array of A. To do this, we use suffix links in suffix ways and we developed efficient algorithms for computing the suffix links. Efficient computation of suffix links is another contribution of this paper because it can be used to solve other problems occurred in bioinformatics that should search all suffixes of a given string in the suffix array of another string such as computing matching statistics, finding longest common substrings, and so on. The experimental results show that our methods for computing suffix links is about 3-4 times faster than the previous fastest methods.