문자열 집합의 순위주기와 순위경계 병렬 계산 (Parallel Computation of Order-Preserving Periods and Order-Preserving Borders of a Set of Strings)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 / 46권 / 12호 / 1232 ~ 1240페이지
· 저자명 : 김영호, 심정섭

초록

정수알파벳으로 구성된 같은 길이의 두 문자열이 주어졌을 때, 두 문자열의 상대적인 순위가 같으면 두 문자열은 순위동형이라 한다. 문자열 Ｔ(lＴl=ｎ)의 접두사 Ｔ[1..ｐ](1≤ｐ≤ｎ)와 순위동형인 문자열이 Ｔ에서 주기적으로 반복되어 나타나면, Ｔ[1..ｐ]의 순위관계표현을 Ｔ의 순위주기라 한다. 만약 Ｔ의 접두사 Ｔ[1..ｑ](1≤ｑ≤ｎ)와 접미사 Ｔ[ｎ-ｑ+1..ｎ]이 서로 순위동형이면, Ｔ[1..ｑ]의 순위관계표현을 Ｔ의 순위경계라 한다. Ｔ의 모든 순위주기, 순위경계의 길이는 Ｚ-함수를 이용하여 각각 Ｏ(ｎlogｎ) 시간에 계산할 수 있다. 본 논문에서는 정수알파벳으로 구성된 길이가 ｎ인 문자열들의 집합 Ｓ={Ｓ₁,Ｓ₂…,Ｓr}이 주어졌을 때, Ｓ의 모든 순위주기, 순위경계의 길이를 각각 Ｏ(rｎ)개의 스레드를 이용하여 Ｏ(ｎ) 시간에 계산하는 Ｚ-함수 기반 병렬알고리즘을 제시한다. 실험결과, r=1,000, ｎ=10,000일 때, 다우존스지수 데이터에 대해 Ｓ의 모든 순위주기, 순위경계의 길이를 계산하는 병렬알고리즘은 각각 기존의 순차알고리즘보다 약 3.47배, 약 3.41배 빠르게 수행되었다.

영어초록

Given two strings of the same length over an integer alphabet, those two strings are order-isomorphic when they have the same relative ranks. When strings order-isomorphic to Ｔ[1..ｐ](1≤ｐ≤ｎ) are periodically repeated in Ｔ, a representation of the order relations of Ｔ[1..ｐ] is referred to as an order-preserving period of Ｔ. When a prefix Ｔ[1..ｑ](1≤ｑ≤ｎ) of Ｔ is order-isomorphic to a suffix Ｔ[ｎ-ｑ+1..ｎ] of Ｔ, a representation of the order relations of Ｔ[1..ｑ] is called an order-preserving border of Ｔ. The lengths of all order-preserving periods (resp. all order-preserving borders) of Ｔ can be computed in Ｏ(ｎlogｎ) time using the Ｚ-function. Given a set Ｓ={Ｓ₁,Ｓ₂…,Ｓr} of strings of length ｎ over an integer alphabet, we propose parallel algorithms computing the lengths of all order-preserving periods and all order-preserving borders of Ｓ using Ｏ(rｎ) threads in Ｏ(ｎ) time by the Ｚ-function. When compared to each sequential algorithm for Dow Jones Industrial Average, the experimental results show that our parallel algorithm for computing the lengths of all order-preserving periods (resp. all order-preserving borders) of Ｓ runs approximately 3.47 (resp. 3.41) times faster when r=1,000, ｎ=10,000.

참고자료

· 없음