earticle

영어

The edit distance metric is one of the most widely used scoring metric for the approximate string matching. Given two strings with lengths m and n, we can compute the edit distance between them in O(mn) time using dynamic programming technique. There are several algorithms for the edit distance problem and some of them are parallel algorithms. In this paper, we present two MapReduce algorithms for the edit distance problem between two strings. We convert the Wagner and Fischer algorithm and the Four-Russians algorithms to the MapReduce algorithms and explain them. In addition, we explain some theoretical analysis for our algorithms using a cost model for MapReduce.

한국어

편집거리는 근사문자열매칭의 대표적인 점수척도로, 길이가 m, n인 두 문자열에 대한 편집거리는 동적프로그래밍 을 이용하여 O(mn) 시간에 계산할 수 있다. 편집거리 계산을 위한 다양한 알고리즘이 연구되고 있으며 그 중에는 병렬 알고리즘에 대한 연구도 포함되어 있다. 본 논문에서는 두 문자열에 대한 편집거리를 계산하는 맵리듀스 알고 리즘을 제시한다. O(mn) 시간에 동작하는 Wagner와 Fischer의 알고리즘과 O(mn/t) 시간에 동작하는 4-러 시안 알고리즘을 각각 맵리듀스 알고리즘으로 변환하고 설명한다. 그리고 맵리듀스 알고리즘들에 대한 이론적인 비용 분석과 함께 제안하는 알고리즘들이 순차 알고리즘보다 시간 효율성을 갖기 위한 조건도 제시한다.