디지털 라이브러리[ 검색결과 ]
k-배율 순위패턴매칭문제를 해결하는 알고리즘
http://doi.org/10.5626/JOK.2022.49.8.585
두 문자열의 길이가 같고 문자열 내에서 같은 위치의 문자들의 상대적 순위가 모두 동일하면 두 문자열은 순위동형이다. 순위패턴매칭문제는 길이가 n인 문자열 T와 길이가 m인 문자열 P가 주어졌을 때, P와 순위동형인 T의 모든 부분문자열을 찾는 문제이다. 순위패턴매칭은 주가지수 분석, 멜로디 분석과 같은 시계열데이터 분석에 활용될 수 있다. 본 논문에서는 순위패턴매칭을 확장한 k-배율 순위패턴매칭문제를 정의하고, 이 문제를 O(n+mlogm) 시간에 해결하는 알고리즘을 제시한다. 또한, O(n+m) 개의 스레드를 사용하여 O(m+k) 시간에 k-배율 순위패턴매칭문제를 해결하는 병렬알고리즘을 제시한다.
사각망 순열패턴매칭 문제에 대한 병렬알고리즘
http://doi.org/10.5626/JOK.2019.46.4.299
사각망 순열패턴매칭은 텍스트 T(|T|= n)와 패턴 P(|P|= m)가 주어졌을 때, P와 순위동형인 T의 모든 사각망 부분서열을 찾는 문제이다. 본 논문에서는 사각망 순열패턴매칭문제를 해결하는 두 가지 병렬알고리즘을 제시한다. 먼저 O(n)개의 스레드를 사용하여 O(nm) 시간에 해결하는 병렬알고리즘을 제시한 후, O(nm)개의 스레드를 사용하여 O(n) 시간에 해결하는 병렬알고리즘을 제시한다. 다우존스 지수 데이터에 대한 실험결과, n = 36, 364 m = 30일 때, 순위통계트리를 사용한 순차알고리즘에 비해 첫번째 병렬알고리즘은 약 7.2배 빠른 수행시간을 보였고, 두 번째 병렬알고리즘은 약 20.6배 빠른 수행시간을 보였다.
2개의 q-그램에 대한 핑거프린트를 이용한 순위패턴매칭알고리즘
http://doi.org/10.5626/JOK.2018.45.11.1111
순위패턴매칭문제는 길이가 각각 n, m인 텍스트 T와 패턴 P가 주어졌을 때, P와 순위가 같은 T의 모든 부분문자열을 찾는 문제이다. 최근 q-그램의 핑거프린트를 이용한 O(nm + nqlogq +q!) 시간 순위패턴매칭 알고리즘이 제시되었다. 본 논문에서는 2개의 q-그램에 대한 핑거프린트를 이용하여 수행시간을 개선한 순위패턴매칭 알고리즘을 제시한다. 실험 결과, 본 논문에서 제시하는 알고리즘은 기존의 알고리즘보다 무작위로 생성된 T(n = 5,000,000)와 P(m = 5,10,15)에 대해 최대 약 12% 빠르게 수행된다. 또한 다우존스지수 데이터를 이용한 T(n = 34,658)와 T에서 무작위로 추출한 P(m = 5,10,15)에 대해 최대 약 10% 빠르게 수행된다.
