초록

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

Approximate pattern matching, a natural extension of exact pattern matching, is allowing errors. It has been studied in such diverse fields as data compression, computer security and bioinformatics. The Hamming distance is one of the well-known distance functions being used to measure the errors bet...

Approximate pattern matching, a natural extension of exact pattern matching, is allowing errors. It has been studied in such diverse fields as data compression, computer security and bioinformatics. The Hamming distance is one of the well-known distance functions being used to measure the errors between two strings of length n, which can be computed in O(n) time. The (Hamming distance based) approximate pattern matching problem of pattern P(${\mid}p{\mid}$=m) and text T(${\mid}T{\mid}$=n) is finding Hamming distances between P and all substrings of T whose lengths are m. The approximate pattern matching problem can be easily solved in O(mn) time using a naive approach. By transforming the approximate pattern matching problem into the polynomial multiplication problem, Amir et al. proposed an O(${\mid}{\sum}{\mid}$nlogm) time algorithm (PM algorithm for short) where ${\mid}{\sum}{\mid}$ is the size of the alphabet. In this paper, we propose a CUDA implementation of a parallelized PM algorithm (PPM algorithm for short) running in O(${\mid}{\sum}{\mid}$logm)time. The experimental results show that the PPM algorithm runs about 40~2,000 times faster than the PM algorithm and runs upto 7,000 times faster than the naive approach, respectively.

주제어