k-배율 순위패턴매칭문제를 해결하는 알고리즘 


49권  8호, pp. 585-592, 8월  2022
10.5626/JOK.2022.49.8.585


PDF

  요약

두 문자열의 길이가 같고 문자열 내에서 같은 위치의 문자들의 상대적 순위가 모두 동일하면 두 문자열은 순위동형이다. 순위패턴매칭문제는 길이가 n인 문자열 T와 길이가 m인 문자열 P가 주어졌을 때, P와 순위동형인 T의 모든 부분문자열을 찾는 문제이다. 순위패턴매칭은 주가지수 분석, 멜로디 분석과 같은 시계열데이터 분석에 활용될 수 있다. 본 논문에서는 순위패턴매칭을 확장한 k-배율 순위패턴매칭문제를 정의하고, 이 문제를 O(n+mlogm) 시간에 해결하는 알고리즘을 제시한다. 또한, O(n+m) 개의 스레드를 사용하여 O(m+k) 시간에 k-배율 순위패턴매칭문제를 해결하는 병렬알고리즘을 제시한다.


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

[IEEE Style]

K. B. Park, Y. Kim, J. C. Na, J. S. Sim, "Algorithms for the k-Scaled Order-Preserving Pattern Matching Problem," Journal of KIISE, JOK, vol. 49, no. 8, pp. 585-592, 2022. DOI: 10.5626/JOK.2022.49.8.585.


[ACM Style]

Kyung Bin Park, Youngho Kim, Joong Cha Na, and Jeong Seop Sim. 2022. Algorithms for the k-Scaled Order-Preserving Pattern Matching Problem. Journal of KIISE, JOK, 49, 8, (2022), 585-592. DOI: 10.5626/JOK.2022.49.8.585.


[KCI Style]

박경빈, 김영호, 나중채, 심정섭, "k-배율 순위패턴매칭문제를 해결하는 알고리즘," 한국정보과학회 논문지, 제49권, 제8호, 585~592쪽, 2022. DOI: 10.5626/JOK.2022.49.8.585.


[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