A Novel Parallel Algorithm for Edit Distance Computation

  • Muhammad Murtaza Yousaf Punjab University College of Information Technology, University of the Punjab, Lahore
  • Muhammad Umair Sadiq Punjab University College of Information Technology, University of the Punjab, Lahore
  • Laeeq Aslam Punjab University College of Information Technology, University of the Punjab, Lahore
  • Waqar ul Qounain Punjab University College of Information Technology, University of the Punjab, Lahore
  • Shahzad Sarwar Punjab University College of Information Technology, University of the Punjab, Lahore

Abstract

The edit distance between two sequences is the minimum number of weighted transformation-operations that are required to transform one string into the other. The weighted transformation-operations are insert, remove, and substitute. Dynamic programming solution to find edit distance exists but it becomes computationally intensive when the lengths of strings become very large. This work presents a novel parallel algorithm to solve edit distance problem of string matching. The algorithm is based on resolving dependencies in the dynamic programming solution of the problem and it is able to compute each row of edit distance table in parallel. In this way, it becomes possible to compute the complete table in min(m,n) iterations for strings of size m and n whereas state-of-the-art parallel algorithm solves the problem in max(m,n) iterations. The proposed algorithm also increases the amount of parallelism in each of its iteration. The algorithm is also capable of exploiting spatial locality while its implementation. Additionally, the algorithm works in a load balanced way that further improves its performance. The algorithm is implemented for multicore systems having shared memory. Implementation of the algorithm in OpenMP shows linear speedup and better execution time as compared to state-of-the-art parallel approach. Efficiency of the algorithm is also proven better in comparison to its competitor.

Published
Jan 1, 2018
How to Cite
YOUSAF, Muhammad Murtaza et al. A Novel Parallel Algorithm for Edit Distance Computation. Mehran University Research Journal of Engineering and Technology, [S.l.], v. 37, n. 1, p. 10, jan. 2018. ISSN 2413-7219. Available at: <http://publications.muet.edu.pk/index.php/muetrj/article/view/125>. Date accessed: 17 jan. 2018.