문자열의 suffix-prefix가 일치하는 모든 쌍 찾기를 위한 상수시간 RMESH 알고리즘
Constant Time RMESH Algorithm for Finding All-pairs Suffix-prefix Matching of Strings
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
문자열 연산이 계산 생물학 분야에 응용되면서 효율적인 문자열 연산을 위한 다양한 자료구조와 알고리즘이 연구되고 있다. suffix-prefix가 일치하는 모든 쌍 찾기는 두 개 이상의 문자열이 주어질 때 각 쌍의 문자열에 대해 가장 긴 suffix와 일치하는 prefix를 찾는 것으로 가장 짧은 슈퍼스트링을 검출하는 근사 알고리즘에서 사용될 뿐만 아니라 생물정보학, 데이터 압축 분야에서도 중요하게 사용된다. 본 논문에서는 RMESH(Reconfigurable MESH) 구조에서 3-차원 프로세서를 사용하여 문자열들의 suffix-prefix가 일치하는 모든 쌍 찾기를 위한 알고리즘을 제안하며, 이 알고리즘은 시간 복잡도를 갖는다.
Abstract
Since string operations were applied to computational biology area, various data structures and algorithms for computing efficient string operations have been studied. The all-pairs suffix-prefix matching is to find the longest suffix and prefix among given strings. The matching algorithm is importantly used for fast approximation algorithm to find the shortest superstring, as well as for bio-informatics and data compressions. In this paper, we present an algorithm to find all-pairs suffix-prefix matchings of the given strings using three-dimensional processors on RMESH(Reconfigurable MESH). The algorithm has time complexity.
참고문헌 (17)
- 김경훈, "RMESH 구조에서 unaligned 선형 사진트리의 alignment를 위한 상수시간 알고리즘", 정보과학회논문지 : 시스템 및 이론, 31(1), pp.10~18 (2004), 한국정보과학회
- 우진운, "문자열의 최대 palindrome을 구하기 위한 상수시간 RMESH 알고리즘", 한국지식정보기술학회 논문지, 5(2), pp.59~67 (2010), 한국지식정보기술학회
- 이상구, "OpenMP를 이용한 새로운 COG 방식의 고속 병렬 퍼지 제어기", 한국지식정보기술학회 논문지, 5(1), pp.77~84 (2010), 한국지식정보기술학회
- 한선미, "문자열의 최장 공통 부분문자열과 최대 반복자를 구하기 위한 상수시간 RMESH 알고리즘", 정보처리학회논문지. 컴퓨터 및 통신시스템, 16(5), pp.319~326 (2009), 한국정보처리학회
- 우진운, "접미사 배열을 이용한 Suffix-Prefix가 일치하는 모든 쌍 찾기", 정보처리학회논문지. 컴퓨터 및 통신시스템, 17(5), pp.221~228 (2010), 한국정보처리학회
- A. Apostolico, "Parallel Construction of a Suffix Tree with Application", Algorithmica, 3, pp.347~365 (1988)
- D. Gusfield, "Algorithms on Strings, Trees, and Sequences, In Computer Science and Computational Biology" (1997), CamBridge University Press
- G. Landau, "Fast parallel and serial approximate string matching", J. of Algorithms, 10, pp.157~169 (1989)
- H. Lee, "RMESH Algorithms for Parallel String Matching", International Symposium on Parallel Architectures, Algorithms and Networks, pp.223~226 (1997)
- J. Jang, "A Fast Algorithm for Computing Histogram on a Reconfigurable Mesh", IEEE Trans. on Pattern Analysis and Machine Intelligence, 17(2), pp.97~106 (1995)
- M. Nigam, "Sorting n Numbers On Reconfigurable Meshes With Buses", Proceedings 7th Intern`ational Parallel Processing Symposium, pp.174~181 (1993)
- P. Green, "Ancient conserved regions in new gene sequences and the protein databases", Science, 259, pp.1711~1716 (1993)
- R. A. Wagner, Michael, "The String-to-String Correction Problem", Journal of the ACM (JACM), 21(1), pp.168~173 (1974)
- R. Miller, "Parallel Computation on Reconfigurable Meshes", IEEE Transactions on Computers, 42(6), pp.678~692 (1993)
- W. Masek, "A fast algorithm computing string edit distances", J. of Computer and System Sciences, 20(1), pp.13~31 (1980)
- Z. Galil, "A Constant Time Optimal Parallel String Matching Algorithm", J. of ACM, 42, pp.908~918 (1995)
- Z. M. Kedem, "Parallel suffix-prefix-Matching Algorithm and Applications", SIAM Journal on Computing, 25(5), pp.998~1023 (1996)