문자열의 최대 palindrome을 구하기 위한 상수시간 RMESH 알고리즘
Constant Time RMESH Algorithm for Finding Maximal Palindromes of String
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
문자열 연산이 계산 생물학 분야에 응용되면서 효율적인 문자열 연산을 위한 다양한 자료구조와 알고리즘이 연구되고 있다. 최대 palindrome을 구하는 문제는 주어진 문자열에서 좌우 대칭인 최대 부분문자열을 찾는 연산이다. 이 연산은 패턴 매칭, 유사도 측정 등의 문자열 처리 분야에서 중요하게 사용되고 있다. 본 논문에서는 RMESH(Reconfigurable MESH) 구조에서 3-차원 n×n×n 프로세서를 사용하여 문자열의 최대 palindrome을 구하는 알고리즘을 제안하며, 이 알고리즘은 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 maximal palindrome problem is an operation to find the maximal symmetric substrings in a string. This operation is importantly used in the string processing area such as pattern matching and likelihood measurement. In this paper, we present an algorithm to compute the maximal palindromes of the given string using three-dimensional n×n×n processors on RMESH(Reconfigurable MESH). The algorithm has O(1) constant time complexity, which is usefully used in the massive data processing areas like the computational biology.
참고문헌 (17)
- 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)
- 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)
- W. Masek, "A fast algorithm computing string edit distances", J. of Computer and System Sciences, 20(1), pp.13~31 (1980)
- 한선미, "문자열의 최장 공통 부분문자열과 최대 반복자를 구하기 위한 상수시간 RMESH 알고리즘", 정보처리학회논문지A, 16(5), pp.319~326 (2009), 한국정보처리학회
- 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)
- H. Lee, "RMESH Algorithms for Parallel String Matching", International Symposium on Parallel Architectures, Algorithms and Networks, pp.223~226 (1997)
- Y. Jiang, "O(k) parallel algorithms for approximate string matching", Neural, 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)
- R. Miller, "Parallel Computation on Reconfigurable Meshes", IEEE Transactions on Computers, 42(6), pp.678~692 (1993)
- 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)
- 김경훈, "RMESH 구조에서 unaligned 선형 사진트리의 alignment를 위한 상수시간 알고리즘", 정보과학회논문지 : 시스템 및 이론, 31(1), pp.10~18 (2004), 한국정보과학회
- R. A. Wagner, "The String-to-String Correction Problem", Journal of the ACM (JACM), 21(1), pp.168~173 (1974)
- M. Nigam, "Sorting Numbers On Reconfigurable Meshes With Buses", Proceedings 7th International Parallel Processing Symposium, pp.174~181 (1993)
- 김석훈, "가중퍼지시스템의 신뢰도 분석을 위한 사다리꼴 모호집합의 사용", 한국지식정보기술학회 논문지, 4(3), pp.43~51 (2009), 한국지식정보기술학회
- 이상구, "OpenMP를 이용한 새로운 COG 방식의 고속 병렬 퍼지 제어기", 한국지식정보기술학회 논문지, 5(1), pp.77~84 (2010), 한국지식정보기술학회