지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 저널정보
- Korean Institute of Information Scientists and Engineers Journal of KIISE Journal of KIISE Vol.49 No.7
- 발행연도
- 2022.7
- 수록면
- 507 - 513 (7page)
- DOI
- 10.5626/JOK.2022.49.7.507
이용수
초록· 키워드
오류제보하기
극대 공통 부분 서열(Maximal Common Subsequence, MCS)은 어떤 문자라도 추가하면 더 이상 공통 조건을 만족하지 않는 공통 부분 서열이다. 최근에 두 문자열의 MCS를 찾는 알고리즘이 제시되었는데, 이 알고리즘은 제곱 시간이 걸리는 최장 공통 부분 서열(Longest Common Subsequence, LCS) 계산 알고리즘에 비해 매우 빠르다. 하지만 이 알고리즘에 의해 계산된 MCS는 LCS보다 훨씬 짧다는 것이 실험적으로 밝혀졌다. 본 논문에서는 기존 알고리즘을 개선하여 더 긴 MCS를 찾는 두 가지 알고리즘을 제시하고, 다양한 실제 데이터와 랜덤 생성 데이터에 대한 실험을 통해 성능의 개선을 확인한다. 본 논문에서 제시한 알고리즘은 실제 데이터에서는 1.47～3.17배, 랜덤 데이터에서는 1.50～3.08배 길이의 MCS를 찾는다.
목차
요약
Abstract
1. 서론
2. 배경 지식
3. 알고리즘 개선
4. 실험 및 결과
5. 결론 및 향후 연구
References
참고문헌 (14)
참고문헌 신청
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, 3rd. ed., The MIT Press, 2009.
L. Bergroth, H. Hakonen, and T. Raita, "A Survey of Longest Common Subsequence Algorithms," Proc. Seventh International Symposium on String Processing and Information Retrieval. SPIRE 2000, pp. 39-48, 2000.
Y. Sakai, "Maximal common subsequence algorithms," Theoretical Computer Science, Vol. 793, pp. 132-139, 2019.
R. A. Wagner and M. J. Fischer, "The String-to-String Correction Problem," Journal of the ACM, Vol. 21, No. 1, pp. 168-173, 1974.
D. S. Hirschberg, "A linear space algorithm for computing maximal common subsequences," Communications of the ACM, Vol. 18, No. 6, pp. 341-343, 1975.
L. Bergroth, H. Hakonen, and T. Raita, "A Survey of Longest Common Subsequence Algorithms," Proc. Seventh International Symposium on String Processing and Information Retrieval. SPIRE 2000, pp. 39-48, 2000.
Y. Sakai, "Maximal common subsequence algorithms," Theoretical Computer Science, Vol. 793, pp. 132-139, 2019.
R. A. Wagner and M. J. Fischer, "The String-to-String Correction Problem," Journal of the ACM, Vol. 21, No. 1, pp. 168-173, 1974.
D. S. Hirschberg, "A linear space algorithm for computing maximal common subsequences," Communications of the ACM, Vol. 18, No. 6, pp. 341-343, 1975.
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
극대 공통 부분 서열 알고리즘을 개선하기 위한 간단한 전략
한국정보과학회 학술발표논문집
2021 .12
-
An Improved Algorithm of Finding a Maximal Common Subsequence
Journal of KIISE
2023 .09
-
[우수논문] 두 문자열의 극대공통부분서열을 찾는 새로운 알고리즘
한국정보과학회 학술발표논문집
2022 .12
-
최장 공통 부분 수열을 이용한 반복 동작 검출 기법
정보과학회 컴퓨팅의 실제 논문지
2022 .04
-
Enumerating Subsequences of a Sequence and Paths of a Tree in the Order of Weight
Journal of Computing Science and Engineering
2019 .03
-
국내 유명 MC들에 대한 음성 특징 분석
한국통신학회 학술대회논문집
2015 .06
-
MC 기법을 이용한 수소 탱크 충전 성능 향상에 관한 연구
한국수소및신에너지학회논문집
2023 .10
-
Feasibility Analysis of AI Algorithms for MCS Selection in Wireless Communication Systems
한국통신학회 학술대회논문집
2020 .02
-
i4mC-NN: Identification of 4mC sites in Rosaceae Genome Using Neural Network Architecture With Multiple Encoding Schemes
제어로봇시스템학회 국제학술대회 논문집
2022 .11
-
최장 공통 부분 수열을 이용한 반복 동작 검출 기법
한국정보과학회 학술발표논문집
2021 .06
-
MCS에 의한 구조물의 지진취약도 곡선 산정 프로그램 개발
한국에너지학회 학술발표회
2024 .10
-
LC/MC형 UAM 항공기 오토파일럿 설계
항공우주시스템공학회 학술행사 논문집
2024 .10
-
MCS에 의한 해석기반 기기의 지진취약도 곡선 산정 프로그램 개발
한국에너지학회 학술발표회
2024 .10
-
On-the-Fly Estimation Strategy for Uncertainty Propagation in Two-Step Monte Carlo Calculation for Residual Radiation Analysis
Nuclear Engineering and Technology
2016 .06
-
시험기반 기기의 MCS 지진취약도 곡선 산정 프로그램 개발
한국에너지학회 학술발표회
2024 .10
-
다중 안테나를 사용하는 이동통신 시스템에서 CNN 기반 송신 안테나 및 MCS 선택
한국통신학회논문지
2023 .09
-
DNA N4- methylcytosine sites prediction using Convolutional Neural Network
대한전자공학회 학술대회
2020 .08
-
최장 공통 부분 수열을 이용한 반복 동작의 횟수 카운트 기법
한국정보과학회 학술발표논문집
2021 .12
-
Simulations of BEAVRS benchmark cycle 2 depletion with MCS/CTF coupling system
Nuclear Engineering and Technology
2020 .01
-
열처리에 따른 Mar-M 247의 특성 변화
한국추진공학회 학술대회논문집
2016 .05
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0