Abstract
This paper presents a parallel algorithm for solving the edit distance problem. The edit distance represents a similarity of two strings and the dynamic programming approach is a general paradigm to compute an edit distancie. There exists an efficient method of parallel computation which is based on bit-operations, however the computation in this method is very complex. In this paper, a simple parallel-algorithm for a single processor is proposed. Moreover, our algorithm can be applied to the alignment problem.
| Original language | English |
|---|---|
| Pages (from-to) | 1-6 |
| Number of pages | 6 |
| Journal | Research Reports on Information Science and Electrical Engineering of Kyushu University |
| Volume | 12 |
| Issue number | 1 |
| Publication status | Published - Mar 2007 |
| Externally published | Yes |
Keywords
- Bit-operation
- Dynamic programming approach
- Edit distance
- Parallel computation
- Time complexity
ASJC Scopus subject areas
- Computer Science(all)
- Electrical and Electronic Engineering