디지털 라이브러리[ 검색결과 ]
Karp-Rabin 알고리즘을 이용한 순위다중패턴매칭 알고리즘의 병렬 구현
http://doi.org/10.5626/JOK.2021.48.3.249
길이가 같은 두 문자열은 각 문자의 상대적 순위가 모두 일치할 때 순위동형이라 한다. 순위다중패턴매칭문제는 텍스트 T(｜T｜=n)와 패턴들의 집합 P̃={P₁,P₂,...,Pk}가 주어졌을 때, P̃의 패턴들과 순위동형인 T의 모든 부분문자열을 찾는 문제이다. 패턴들 중 가장 짧은 패턴의 길이를 m, 가장 긴 패턴의 길이를 m̅, 모든 패턴들의 길이의 합을 M이라 하자. M∈mO(1)인 경우 Karp-Rabin 알고리즘을 이용하여 탐색단계를 평균적으로 O(n)시간에 수행하는 순위다중패턴매칭 알고리즘이 제시되었다. 본 논문에서는 Karp-Rabin 알고리즘을 이용하여 순위다중패턴매칭문제를 병렬적으로 해결하는 구현 방법을 제시한다. 제시하는 병렬 구현은 전처리단계를 O(M)개의 스레드를 사용하여 평균적으로 O(m̅)시간에 수행하며, 탐색단계를 O(n)개의 스레드를 사용하여 평균적으로 O(m)시간에 각각 수행한다. 무작위로 생성된 문자열에 대해 실험한 결과, n=1,000,000, k=1,000, m=5 일 때 본 논문에서 제시하는 병렬 구현이 기존의 순차알고리즘보다 약 201.5배 빠르게 수행되었다.
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배 빠르게 수행되었다.
순위다중패턴매칭을 위한 해싱기반 알고리즘
순위패턴매칭문제는 텍스트 T와 패턴 P가 주어질 때, P와 각 문자들의 순위가 동일한 순서로 나타나는 T의 모든 부분문자열을 찾는 문제이다. 순위패턴매칭문제는 주가지수분석과 음악의 유사성분석과 같이 문자 자체를 비교하는 것보다 값의 변화순서가 중요한 분야에서 연구가 진행되었다. 순위다중패턴매칭문제는 텍스트 T와 여러 개의 패턴들로 이루어진 패턴집합 ℙ가 주어질 때, ℙ에 속한 패턴과 각 문자들의 순위가 동일한 순서로 나타나는 T의 모든 부분문자열을 찾는 문제이다. 본 논문에서는 순위다중 패턴매칭문제를 해결하는 해싱기반 알고리즘을 제시한다.
