김영호  심정섭

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₂,..., S_r｝이 주어졌을 때, S의 모든 순위주기, 순위경계의 길이를 각각 O(rn)개의 스레드를 이용하여 O(n) 시간에 계산하는 Z-함수 기반 병렬알고리즘을 제시한다. 실험결과, r=1,000, n=10,000일 때, 다우존스지수 데이터에 대해 Ŝ의 모든 순위주기, 순위경계의 길이를 계산하는 병렬알고리즘은 각각 기존의 순차알고리즘보다 약 3.47배, 약 3.41배 빠르게 수행되었다.