유사도 측정에 대한 극대 공통 부분 서열의 효용성
Efficacy of Maximal Common Subsequences for Measuring Similarity
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
최장 공통 부분 서열(Longest Common Subsequence, LCS)은 서열의 유사도(similarity)를 나타내는 주요 지표 중 하나로 사용되며, 일반적으로 두 문자열의 LCS를 계산하는 데는 문자열 길이의 곱에 비례하는 시간이 필요하다. 극대 공통 부분 서열(Maximal Common Subsequence, MCS)은 최장(longest) 조건을 극대(maximal)로 완화한 것으로, 최근 두 문자열의 MCS를 선형에 가까운 시간에 찾는 알고리즘이 개발되었다. 두 문자열의 MCS의 길이는 LCS의 길이와 달리 유일하지 않을 수 있으며, LCS의 길이가 매우 길더라도 길이가 1인 MCS가 존재할 수 있다. 따라서 MCS의 유사도로서의 효용성은 어떤 MCS를 찾는지에 따라 달라진다. 본 논문에서는 MCS 알고리즘의 효용성을 알아보기 위해, 다양한 실제 데이터와 랜덤 생성 데이터에 대해 MCS의 길이를 LCS의 길이와 비교하고 상관 관계를 분석한다. MCS의 길이는 LCS 길이 대비 실제 데이터에서는 15.5 ~ 58.0%, 랜덤 데이터에서는 12.6 ~ 55.3%로 나타났고, MCS의 길이와 LCS 길이의 상관 관계도 높지 않았다.
Abstract
The longest common subsequence (LCS for short) is one of the main criteria of measuring sequence similarity. Finding the LCS of two strings requires a time proportional to the product of the lengths of the two strings. The maximal common subsequence (MCS for short) is a variant of the LCS, where the constraint is weakened from longest to maximal. Recently, a (sub)linearithmic-time algorithm for finding an MCS of two strings was proposed. The lengths of MCS’s of two strings may not be identical unlike the lengths of LCS’s. Although the length of the LCS is very long, an MCS of length 1 may exist. Therefore, the efficacy of MCS for measuring similarity depends on which MCS is found. In this paper, in order to examine the efficacy of MCS, we compare the lengths of LCS and MCS and analyze the correlation of the two lengths for various real data and randomly generated data. The ratio of the length of MCS to the length of LCS was 15.5% to 58.0% in the real data and 12.6% to 55.3% in the random data. The correlation between the lengths of MCS and LCS was not high.
참고문헌 (15)
- L. Bergroth, "A Survey of Longest Common Subsequence Algorithms", Proceedings Seventh International Symposium on String Processing and Information Retrieval. SPIRE 2000, pp.39~48 (2000)
- 조호성, "Snort 기반 탐지 규칙의 유사성 분석 프로그램 개발 및 활용", 한국차세대컴퓨팅학회 논문지, 11(1), pp.32~43 (2015), 한국차세대컴퓨팅학회
- 김영호, "k-오차문제를 위한 4-러시안 알고리즘의 계산 단계 병렬화", 한국차세대컴퓨팅학회 논문지, 9(2), pp.78~88 (2013), 한국차세대컴퓨팅학회
- 김진욱, "편집거리 계산을 위한 맵리듀스 알고리즘", 한국차세대컴퓨팅학회 논문지, 11(2), pp.79~89 (2015), 한국차세대컴퓨팅학회
- Robert A. Wagner, "The String-to-String Correction Problem", Journal of the ACM, 21(1), pp.168~173 (1974)
- D. S. Hirschberg, "A linear space algorithm for computing maximal common subsequences", Communications of the ACM, 18(6), pp.341~343 (1975)
- R. Impagliazzo, "On the complexity of k-SAT", Journal of Computer and System Sciences, 62(2), pp.367~375 (2001)
- R. Impagliazzo, "Which problems have strongly exponential complexity?", Journal of Computer and System Sciences, 63(4), pp.512~530 (2001)
- A. Abboud, "Tight Hardness Results for LCS and Other Sequence Similarity Measures", 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp.59~78 (2015)
- K. Bringmann, "Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping", 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp.79~97 (2015)
- Y. Sakai, "Maximal common subsequence algorithms", Theoretical Computer Science, 793, pp.132~139 (2019)
- C. B. Fraser, "Maximal Common Subsequences and Minimal Common Supersequences", Information and Computation, 124(2), pp.145~153 (1996)
- A. Conte, "Enumeration of Maximal Common Subsequences Between Two Strings", Algorithmica, 84(3), pp.757~783 (2022)
- [URL]