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배 빠른 결과를 보였다.

목차

요약
 Abstract
 1. 서론
 2. 관련 연구
  2.1 문자열과 거리함수
  2.2 k-오차문제 해결 알고리즘
  2.3 4-러시안 알고리즘
 3. k-오차문제 병렬계산
 4. 실험 결과 및 분석
  4.1 전처리 단계의 실험 결과
  4.2 계산 단계의 실험 결과
 5. 결론
 참고문헌

키워드

저자

• 김영호 [ Young Ho Kim | 인하대학교 컴퓨터정보공학부 ]
• 김진욱 [ Jin Wook Kim | 서울대학교병원 의료정보센터 ]
• 심정섭 [ Jeong Seop Sim | 인하대학교 컴퓨터정보공학부 ] 교신저자

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국차세대컴퓨팅학회 논문지 [THE JOURNAL OF KOREAN INSTITUTE OF NEXT GENERATION COMPUTING]

• 간기

  격월간

• pISSN

  1975-681X

• 수록기간

  2005~2026

• 등재여부

  KCI 등재

• 십진분류

  KDC 566 DDC 004