earticle

영어

Approximate string matching problems have been studied extensively for a long time. Two of the most well-known approximate string matching problems are the edit distance problem and the k -difference problem. Given two strings P(lPl=m) and T(lTl=n) over an alphabet Σ , the edit distance problem is to compute the edit distance between P and T . The k-difference problem is to find all the occurrences of P in T with at most k edit distances. The edit distance problem and the k-difference problem can be solved in O(mn) time using dynamic programming technique. If suffix trees are used, the k-difference problem can be solved in O(kn) time and space. The edit distance problem also can be solved using Four-Russians’ algorithm whose preprocessing step runs in O((3lΣl)2tt2) time and O((3lΣl)2tt) space and the computation step runs in O(mn/t) time and O(mn) space where t is the size of the block. In this paper, we propose a parallelized version of the computation step of the Four-Russians’ algorithm for the k-difference problem which runs in O(m+n) time using m/t threads. For DNA alphabet, experimental results show that our parallel algorithm is about 41 times and 19 times faster than the (sequential) Four-Russians’ algorithm when t=2 and t=4, respectively. For binary alphabet, our parallel algorithm is about 45 times and 15 times faster than the (sequential) Four-Russians’ algorithm when t=2 and t=5, respectively.

한국어

근사문자열매칭문제는 오랫동안 활발히 연구되어 왔다. 대표적인 근사문자열매칭문제로 편집거리문제와 k-오차문 제가 잘 알려져 있다. 알파벳 Σ에 대해 길이가 각각 m, n인 두 문자열 P와 T가 주어졌을 때, 편집거리문제는 P와 T사이의 편집거리를 계산하는 문제이며, k-오차문제는 T내에서 P가 k이내의 편집거리로 발생하는 모든 위치를 찾는 문제이다. 편집거리문제와 k-오차문제는 동적프로그래밍을 이용하여 O(mn) 시간과 공간을 이용하여 해결할 수 있으며, 접미사트리를 이용하면 k-오차문제는 O(kn) 시간과 공간을 이용하여 해결할 수 있다. 편집 거리 문제는 4-러시안 알고리즘을 이용해서도 해결할 수 있다. 4-러시안 알고리즘은 블록 크기를 t라 할 때, 전처리 단 계에서 O((3lΣl)2tt2) 시간과 O((3lΣl)2tt) 공간, 계산 단계에서 O(mm/t) 시간과 O(mn) 공간을 이용하여 편집거 리를 계산한다. 본 논문에서는 4-러시안 알고리즘의 계산 단계를 m/t 개의 쓰레드를 사용하여 O(m+n) 시간에 수 행하도록 병렬화하여 k-오차문제를 해결하는 알고리즘을 제시한다. 실험결과, 제시된 4-러시안 병렬알고리즘은 기존의 4-러시안 순차알고리즘보다 DNA알파벳(lΣl = 4)의 경우 t = 2일 때 약 41배, t = 4일 때 약 19배 빠른 결과를 보였고, 이진알파벳(lΣl = 2)의 경우 t = 2일 때 약 45배, t = 5일 때 약 15배 빠른 결과를 보였다.