부산대학교 도서관

길이가 같은 두 문자열의 같은 위치에 있는 문자의 순위가 모두 일치할 때, 두 문자열은 순위동형이라 한다. 순위다중패턴매칭문제는 텍스트 T 와 K개의 패턴들의 집합 P′ = {P1,P2…PK}이 주어졌을 때, P′의 패턴들과 순위동형인 T의 모든 부분문자열의 위치를 찾는 문제이다. 최근 전처리단계에서 P ′에 대한 이동테이블을 O(kmqlogq) 시간에 계산하여 순위다중패턴매칭문제를 해결하는 해싱기반 알고리즘이 제시되었다. 이때 p′에서 가장 짧은 패턴의 길이를 m, q-그램의 길이를 q라고 한다. 본 논문에서는 p′이 주어졌을 때, 이동테이블을 O(mqlogq) 시간에 계산하는 병렬알고리즘을 제시한다. 실험결과, 본 논문에서 제시하는 병렬알고리즘은 k개의 스레드를 이용하여 m = 100, q =5에 대해 k = 100일 때와 k= 1,000일 때 순차알고리즘보다 각각 약 12.9배, 약 215배 빠른 수행시간을 보였다.