더 긴 극대 공통 부분 서열을 찾기 위한 알고리즘 


49권  7호, pp. 507-513, 7월  2022
10.5626/JOK.2022.49.7.507


PDF

  요약

극대 공통 부분 서열(Maximal Common Subsequence, MCS)은 어떤 문자라도 추가하면 더 이상 공통 조건을 만족하지 않는 공통 부분 서열이다. 최근에 두 문자열의 MCS를 찾는 알고리즘이 제시되었는데, 이 알고리즘은 제곱 시간이 걸리는 최장 공통 부분 서열(Longest Common Subsequence, LCS) 계산 알고리즘에 비해 매우 빠르다. 하지만 이 알고리즘에 의해 계산된 MCS는 LCS보다 훨씬 짧다는 것이 실험적으로 밝혀졌다. 본 논문에서는 기존 알고리즘을 개선하여 더 긴 MCS를 찾는 두 가지 알고리즘을 제시하고, 다양한 실제 데이터와 랜덤 생성 데이터에 대한 실험을 통해 성능의 개선을 확인한다. 본 논문에서 제시한 알고리즘은 실제 데이터에서는 1.47～3.17배, 랜덤 데이터에서는 1.50～3.08배 길이의 MCS를 찾는다.


  통계
2022년 11월부터 누적 집계
동일한 세션일 때 여러 번 접속해도 한 번만 카운트됩니다. 그래프 위에 마우스를 올리면 자세한 수치를 확인하실 수 있습니다.
  논문 참조

[IEEE Style]

D. Lee and J. C. Na, "An Improved Algorithm for Finding a Longer Maximal Common Subsequence," Journal of KIISE, JOK, vol. 49, no. 7, pp. 507-513, 2022. DOI: 10.5626/JOK.2022.49.7.507.


[ACM Style]

DongYeop Lee and Joong Chae Na. 2022. An Improved Algorithm for Finding a Longer Maximal Common Subsequence. Journal of KIISE, JOK, 49, 7, (2022), 507-513. DOI: 10.5626/JOK.2022.49.7.507.


[KCI Style]

이동엽, 나중채, "더 긴 극대 공통 부분 서열을 찾기 위한 알고리즘," 한국정보과학회 논문지, 제49권, 제7호, 507~513쪽, 2022. DOI: 10.5626/JOK.2022.49.7.507.


[Endnote/Zotero/Mendeley (RIS)]  Download


[BibTeX]  Download



Search




Journal of KIISE

  • ISSN : 2383-630X(Print)
  • ISSN : 2383-6296(Electronic)
  • KCI Accredited Journal

사무국

  • Tel. +82-2-588-9240
  • Fax. +82-2-521-1352
  • E-mail. chwoo@kiise.or.kr