지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학위논문
- 저자정보
- 지도교수
- 나중채
- 발행연도
- 2022
- 저작권
- 세종대학교 논문은 저작권에 의해 보호받습니다.
이용수6
이 논문의 연구 히스토리 (3)
2022
- 이 논문의 후속연구가 궁금하신가요?
- 연관 학술논문 또는 학술발표를 통해 보다 발전된 연구결과를 확인하실 수 있습니다.
- 이 논문의 연구 히스토리 확인하기
초록· 키워드
오류제보하기
최장 공통 부분 서열(Longest Common Subsequence, LCS)은 서열의 유사도(similarity)를 나타내는 주요 지표 중 하나로 사용되며, 일반적으로 두 문자열의 LCS를 구하는 데는 문자열 길이의 곱에 비례하는 시간이 필요하다. 극대 공통 부분 서열(Maximal Common Subsequence, MCS)은 최장(longest) 조건을 극대(maximal)로 완화하여 어떤 문자라도 추가하면 더 이상 공통 조건을 만족시키기 못하는 공통 서열로, 두 문자열의 MCS를 선형에 가까운 시간에 찾는 알고리즘이 최근 제시되었다. 두 문자열의 MCS의 길이는 LCS의 길이와 달리 유일하지 않을 수 있으며, LCS의 길이가 매우 길더라도 길이가 1인 MCS가 존재할 수 있다. 따라서 MCS의 유사도로서의 효용성은 어떤 MCS를 찾는지에 따라 달라진다.
본 논문에서는 첫째, 기존 알고리즘으로 구한 MCS의 효용성을 다양한 실제 데이터와 랜덤으로 생성한 데이터에 대한 실험을 통해 분석한다. MCS의 길이는 LCS 길이 대비 실제 데이터에서는 15.5~58.0%, 랜덤 데이터에서는 12.6~55.3%로 나타났고, MCS의 길이와 LCS의 길이의 상관 관계도 높지 않았다. 둘째, 기존 알고리즘을 개선하여 더 긴 MCS를 찾는 두 가지 알고리즘 (알고리즘 A, 알고리즘 P)을 제시한다. 알고리즘 A는 기존의 MCS 알고리즘에서 공통 문자를 찾는 순서를 변경하는 전략을 사용하고, 알고리즘 P는 공통 문자를 한 번에 한 쌍 처리하는 전략을 사용한다. 개선 알고리즘은 기존 알고리즘 대비 실제 데이터에서는 1.47~3.17배, 랜덤 데이터에서는 1.5~3.08배 길이의 MCS를 찾았다.
본 논문에서는 첫째, 기존 알고리즘으로 구한 MCS의 효용성을 다양한 실제 데이터와 랜덤으로 생성한 데이터에 대한 실험을 통해 분석한다. MCS의 길이는 LCS 길이 대비 실제 데이터에서는 15.5~58.0%, 랜덤 데이터에서는 12.6~55.3%로 나타났고, MCS의 길이와 LCS의 길이의 상관 관계도 높지 않았다. 둘째, 기존 알고리즘을 개선하여 더 긴 MCS를 찾는 두 가지 알고리즘 (알고리즘 A, 알고리즘 P)을 제시한다. 알고리즘 A는 기존의 MCS 알고리즘에서 공통 문자를 찾는 순서를 변경하는 전략을 사용하고, 알고리즘 P는 공통 문자를 한 번에 한 쌍 처리하는 전략을 사용한다. 개선 알고리즘은 기존 알고리즘 대비 실제 데이터에서는 1.47~3.17배, 랜덤 데이터에서는 1.5~3.08배 길이의 MCS를 찾았다.
목차
I. 서론 10II. 배경지식 141. 최장 공통 부분 서열 (LCS) 142. 극대 공통 부분 서열 (MCS) 16III. 극대 공통 부분 서열(MCS)의 효용성 171. 실험 설정 172. MCS와 LCS의 길이 차이 192. 1. 실제 데이터 202. 2. 랜덤 데이터 223. MCS와 LCS 길이의 상관 관계 243. 1. 실제 데이터 243. 2. 랜덤 데이터 254. LCS와 MCS의 시간 비교 27IV. 개선 알고리즘 281. 기존 MCS 알고리즘 282. 개선 알고리즘 A 313. 개선 알고리즘 P 324. 실험 및 분석 334. 1. 길이 비교 344. 1. 1. 실제 데이터 344. 1. 2. 랜덤 데이터 374. 2. 여러 쌍의 문자를 검사하는 알고리즘 P의 길이 차이 42V. 결론 45참고문헌 47
최근 본 자료
댓글(0)
0