디지털 라이브러리[ 검색결과 ]
극대공통부분서열을 찾는 개선된 알고리즘
http://doi.org/10.5626/JOK.2023.50.9.737
두 문자열의 극대공통부분서열(MCS)은 어떤 문자를 삽입하여도 더 긴 공통부분서열을 만들 수 없는 공통부분서열이다. 최장공통부분서열(LCS)과 달리 MCS의 길이는 다양하고, 가장 긴 MCS가 LCS이다. LCS는 일반적으로 두 서열의 유사도를 비교할 때 사용되지만, 계산하는데 매우 긴 시간이 걸린다. MCS는 LCS보다 빠르게 계산할 수 있으므로 더 긴 MCS를 찾는 문제는 중요하다. 길이의 합이 n인 두 문자열 X와 Y의 MCS 중 하나를 O(n) 공간을 이용하여 O(n√(logn/loglogn)) 시간에 계산하는 알고리즘이 제시되었고 이를 개선한 알고리즘들도 제시되었다. 본 논문에서는 기존의 알고리즘들보다 더 많은 문자를 확인하여, 상수 k가 주어졌을 때 O(kn) 공간을 이용하여 O(n√(logn/loglogn)) 시간에 MCS를 계산하는 알고리즘을 제시한다. 실제 데이터와 무작위로 생성한 데이터를 이용하여 실험을 진행한 결과, 본 논문에서 제시한 알고리즘으로 계산된 MCS의 길이가 기존의 알고리즘으로 계산된 MCS보다, 최대 6.31배 길다.
더 긴 극대 공통 부분 서열을 찾기 위한 알고리즘
http://doi.org/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를 찾는다.
