근사문자열매칭 문제는 컴퓨터보안, 검색엔진, 생물정보학과 같은 다양한 분야에서 연구되고 있다. 근사문자열매칭에서는 불일치 정도를 판단하기 위해, 편집거리나 확장편집거리와 같은 거리함수를 이용한다. 알파벳 ${sum}$의 문자들로 구성된, 길이가 각각 m, n인 두 문자열 X, Y의 편집거리는 X를 Y로 변환하기 위해 필요한 최소 편집연산의 수로 정의된다. 이 때 편집연산은 삽입, 삭제, 교체연산으로 구성된다. X, Y의 확장편집거리는 X를 Y로 변환하기 위해 필요한 최소 확장편집연산의 수로 정의된다. 이때, 확장편집연산은 편집연산에 교환연산을 추가한 연산들로 구성된다. X, Y의 확장편집거리는 동적프로그래밍 기법을 이용하여 O(mn) 시간과 공간을 이용하여 계산할 수 있다. 본 논문에서는 X, Y의 확장편집거리를 최대 m개의 쓰레드를 이용하여 O(m+n) 시간과 O(mn) 공간을 이용하여 계산하는 병렬알고리즘을 제시한다. 또한 확장편집거리를 계산하는 순차알고리즘과 병렬알고리즘을 각각 CPU와 GPU 기반으로 구현하여 두 알고리즘의 수행시간을 비교한다. 실험 결과 두 문자열의 길이가 각각 10,000일 때, 병렬알고리즘이 순차알고리즘에 비하여 약 16배 빠른 수행시간을 보였다.
Approximate string matching problems have been studied in such diverse fields as computer security, search engines, and bioinformatics. To measure the amounts of errors between two strings, approximate string matching uses distance functions such as the edit distance and the extended edit distance. Given two strings X and Y (${mid}X{mid}=m$, ${mid}Y{mid}=n$) over an alphabet ${sum}$, the edit distance between X and Y is the minimum number of edit operations to convert X into Y. Edit operations consist of insertions, deletions and changes. The extended edit distance between X and Y is the minimum number of extended edit operations to convert X into Y. Extended edit operations consist of insertions, deletions, changes, and swaps. The edit distance and the extended edit distance between X and Y can be computed using dynamic programming technique in O(mn) time and space. In this paper, we present a parallel algorithm of computing the extended edit distance between two strings. Our algorithm computes the extended edit distance between X and Y in O(m+n) time using m threads where $m{leq}n$. We implemented our parallel algorithm using CUDA. The experimental results show that our algorithm runs about 16 times faster than the sequential algorithm when m = n = 10,000.
