문자열의 최장 공통 부분문자열과 최대 반복자를 구하기 위한 상수시간 RMESH 알고리즘
Constant Time RMESH Algorithm for Computing Longest Common Substring and Maximal Repeat of String
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
문자열 연산이 계산 생물학 분야에 응용되면서 효율적인 문자열 연산을 위한 다양한 자료구조와 알고리즘이 연구되고 있다. 최장 공통 부분문자열 문제는 두 개 이상의 문자열에서 가장 길게 일치하는 부분문자열을 찾는 연산이며, 최대 반복자 문제는 하나의 문자열에서 두 번 이상 반복되는 부분문자열을 찾는 연산이다. 이 연산은 패턴 매칭, 유사도 측정 등의 문자열 처리 분야에서 중요하게 사용되고 있다. 본 논문에서는 RMESH(Reconfigurable MESH) 구조에서 3-차원 n×n×n 프로세서를 사용하여 두 문자열의 최장 공통 부분문자열을 구하는 알고리즘과 주어진 문자열의 최대 반복자를 찾는 알고리즘을 제안하며, 이 알고리즘들은 모두 O(1)시간 복잡도를 갖는다.
Abstract
Since string operations were applied to computational biology area, various data structures and algorithms for computing efficient string operations have been studied. The longest common substring problem is an operation to find the longest matching substring in more than two strings, and maximal repeat of string problem is an operation to find substrings repeated more than once in the given string. These operations are importantly used in the string processing area such as pattern matching and likelihood measurement. In this paper, we present algorithms to compute the longest common substring of two strings and to find the maximal repeat of string using three-dimensional n×n×n processors on RMESH(Reconfigurable MESH). Our algorithms have O(1) time complexity.
참고문헌 (18)
- R. A. Wagner, "The String-to-String Correction Problem", Journal of the ACM (JACM), 21(1), pp.168~173 (1974)
- Dan. Gusfield, "Algorithms on Strings, Trees, and Sequences, Computer Science and Computational Biology" (1997), CamBridge University Press
- S. Needleman, "A general method applicable to the search for similarities in the amino acid sequence of two proteins", J. Mol. BioInformatics, 48(3), pp.443~453 (1970)
- W. Masek, "A fast algorithm computing string edit distances", J. of Computer and System Sciences, 20(1), pp.13~31 (1980)
- 전정은, "써픽스 배열을 이용한 최장 공통 부분스트링 계산", 한국정보과학회 가을 학술발표논문집, 4(2), pp.739~741 (2004)
- I. Lee, "Linear time algorithm for the longest common repeat problem", J. of Discrete Algorithms, 5, pp.243~249 (2006)
- A. Apostolico, "Parallel Construction of a Suffix Tree with Application", Algorithmica, 3, pp.347~365 (1988)
- G. Landau, "Fast parallel and serial approximate string matching", J. of Algorithms, 10, pp.157~169 (1989)
- Y. Jiang, "O(k) parallel algorithms for approximate string matching", Neurla, Parallel and Scientific Computations, 1, pp.443~452 (1993)
- Z. Galil, "A Constant Time Optimal Parallel String Matching Algorithm", J. of ACM, 42, pp.908~918 (1995)
- H. Lee, "RMESH Algorithms for Parallel String Matching", International Symposium on Parallel Architectures, Algorithms and Networks, pp.223~226 (1997)
- A. Datta, "Constant Time Algorithms for String Processing on the Reconfigurable Mesh", The 4th Australasian conference on Parallel and real-time systems, pp.226~237 (1997)
- R. Miller, "Parallel Computation on Reconfigurable Meshes", IEEE Transactions on Computers, 42(6), pp.678~692 (1993)
- 김기원, "선형 사진트리로 표현된 이진 영상의 면적과 둘레 길이를 계산하기 위한 상수시간 RMESH", 한국정보처리학회 논문지, 5(7), pp.1746~1758 (1998)
- 김경훈, "RMESH 구조에서 unaligned 선형 사진트리의 alignment를 위한 상수시간 알고리즘", 정보과학회논문지 : 시스템 및 이론, 31(1), pp.10~18 (2004), 한국정보과학회
- 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)
- Y. Ben-Asher, "The Power of Reconfiguration", Journal of Parallel and Distributed Computing, 13, pp.139~153 (1991)
- M. Nigam, "Sorting Numbers On Reconfigurable Meshes With Buses", Proceedings 7th International Parallel Processing Symposium, pp.174~181 (1993)