http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
Z-함수를 이용한 순위패턴매칭과 순위다중패턴매칭 병렬계산
신유건(Youkun Shin),김영호(Youngho Kim),심정섭(Jeong Seop Sim) 한국정보과학회 2018 정보과학회논문지 Vol.45 No.8
순위패턴매칭문제는 길이가 각각 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배 빠르게 수행되었다. Given a text T of length n and a pattern P of length m, the order-preserving pattern matching problem is to find all substrings in T which are order-isomorphic to P. Given a text T of length n and a set of patterns W={P₁, P₂,…, Pb}, the order-preserving multiple pattern matching problem is to find all substrings in T which are order-isomorphic to patterns of W. In this paper, we present two parallel algorithms based on the Z-function. The first algorithm for the order-preserving pattern matching problem runs in O(m) time using O(n+hm) threads and the second algorithm for the order-preserving multiple pattern matching problem runs in O(n+M) time using O(b(n+M)) threads, where h is the number of blocks and M is the length of the longest pattern in W. Experimental results show that our parallel algorithm for the order-preserving pattern matching problem is approximately 71.2 times faster than the sequential algorithm when m=10 and n=1,000,000, and that our parallel algorithm for the order-preserving multiple pattern matching problem is approximately 12.2 times faster than the sequential algorithm when b=1,000, m=10, and n=1,000.