Current Result Document :
| 한글제목(Korean Title) |
극대 공통 부분 서열 알고리즘을 개선하기 위한 간단한 전략 |
| 영문제목(English Title) |
A Simple Strategy to Improve Maximal Common Subsequence Algorithms |
| 저자(Author) |
탁현
신찬수
Hyun Tarko
Chan-Su Shin
이동엽
나중채
DongYeop Lee
Joong Chae Na
|
| 원문수록처(Citation) |
VOL 48 NO. 902 PP. 1149 ~ 1151 (2021. 12) |
한글내용
(Korean Abstract) |
최근 최장 공통 부분 서열(Longest Common Subsequence, LCS)의 최장(longest) 조건을 극대(maximal)로 완화한 극대 공통 부분 서열(Maximal Common Subsequence, MCS)이 제시되었다. 또 두 문자열의 MCS 중 하나를 선형에 가까운 시간과 선형 공간에 찾는 알고리즘이 제시되었다. 이 알고리즘이 찾는 MCS와 최적해인 LCS의 길이를 비교했을 때 차이가 매우 크다는 연구 결과가 제시되었다. 본 논문에서는 기존 알고리즘의 공통 부분 서열 탐색 방법을 개선하여 LCS의 길이에 더 가까운 길이의 MCS를 찾을 수 있는 방법을 제시하고, DNA 등의 실제 데이터와 랜덤 생성된 데이터에 대한 실험을 통해 성능 개선을 확인했다. 개선된 알고리즘은 기존 알고리즘에 비해 실제 데이터에서는 기존의 알고리즘에 비해 실제 데이터에서는 1.5~3.3배, 랜덤 데이터에서는 1.4~2.7배 더 긴 길이의 MCS를 찾았다. |
영문내용
(English Abstract) |
|
| 키워드(Keyword) |
|
| 파일첨부 |
PDF 다운로드
|
