디지털 라이브러리[ 검색결과 ]
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.12.1232
정수알파벳으로 구성된 같은 길이의 두 문자열이 주어졌을 때, 두 문자열의 상대적인 순위가 같으면 두 문자열은 순위동형이라 한다. 문자열 T(∣T∣=n)의 접두사 T[1..p](1≤p≤n)와 순위동형인 문자열이 T 에서 주기적으로 반복되어 나타나면, T[1..p]의 순위관계표현을 T의 순위주기라 한다. 만약 T의 접두사 T[1..p](1 ≤q ≤ n)와 접미사 T[n-q+1..n]이 서로 순위동형이면, T[1..p]의 순위관계표현을 T의 순위경계라 한다. T의 모든 순위주기, 순위경계의 길이는 Z-함수를 이용하여 각각 O(n log) 시간에 계산할 수 있다. 본 논문에서는 정수알파벳으로 구성된 길이가 n인 문자열들의 집합 Ŝ=｛S₁, S₂,..., Sr｝이 주어졌을 때, S의 모든 순위주기, 순위경계의 길이를 각각 O(rn)개의 스레드를 이용하여 O(n) 시간에 계산하는 Z-함수 기반 병렬알고리즘을 제시한다. 실험결과, r=1,000, n=10,000일 때, 다우존스지수 데이터에 대해 Ŝ의 모든 순위주기, 순위경계의 길이를 계산하는 병렬알고리즘은 각각 기존의 순차알고리즘보다 약 3.47배, 약 3.41배 빠르게 수행되었다.
사각망 순열패턴매칭 문제에 대한 병렬알고리즘
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배 빠른 수행시간을 보였다.
Z-함수를 이용한 순위패턴매칭과 순위다중패턴매칭 병렬계산
http://doi.org/10.5626/JOK.2018.45.8.778
순위패턴매칭문제는 길이가 각각 n, m 인 텍스트 T와 패턴 P가 주어졌을 때, P와 순위동형인 T의 모든 부분문자열의 위치를 찾는 문제이다. 순위다중패턴매칭문제는 길이가 n인 텍스트 T와 패턴 집합 W={P₁, P₂,…, Pb}가 주어졌을 때 W의 패턴들과 순위동형인 T의 모든 부분문자열의 위치를 찾는 문제이다. 본 논문에서는 Z-함수를 기반으로, 순위패턴매칭문제를 O(n+hm)개의 스레드를 사용하여 O(m) 시간에 해결하는 병렬알고리즘과 순위다중패턴매칭문제를 O(b(n+M))개의 스레드를 사용하여 O(n+M) 시간에 해결하는 병렬알고리즘을 제시한다. 이때, h는 블록의 개수이며, M은 W에서 가장 긴 패턴의 길이를 나타낸다. 실험 결과, 순위패턴매칭문제에 대한 병렬알고리즘은 순차알고리즘보다 m=10, n=1,000,000일 때 약 71.2배 빠르게 수행되었다. 또한 순위다중패턴매칭문제에 대한 병렬알고리즘은 b=1,000, m=10, n=1,000일 때 순차알고리즘보다 약 12.2배 빠르게 수행되었다.
정수문자열의 δ-근사주기와 γ-근사주기를 찾는 병렬알고리즘
http://doi.org/10.5626/JOK.2017.44.8.760
반복적인 문자열은 데이터압축, 생물정보학 등 여러 분야에서 연구되어 왔다. 본 논문에서는 음악서열이나 주가지수와 같이 정수로 표현될 수 있는 문자열에 대한 반복에 대해 연구한다. 최근 정수문자열의 최소 δ-근사주기와 최소 γ-근사주기를 찾는 문제들이 소개되었고, 문자열의 길이가 n일 때, 두 문제를 각각 O(n²)시간에 해결하는 알고리즘들이 제시되었다. 본 논문에서는 위의 두 문제에 대해 각각 O(n²)개의 스레드를 이용하여 O(n) 시간에 해결하는 병렬알고리즘을 제시한다. 실험결과, n = 10,000일 때, 본 논문에서 제시하는 병렬알고리즘은 순차알고리즘보다 최소 δ-근사주기를 계산하는데 약 19.7배, 최소 γ-근사주기를 계산하는데 약 40.08배 빠른 수행시간을 보였다.
