A Novel Parallel Algorithm for Edit Distance Computation
Journal: Mehran University Research Journal of Engineering and Technology (Vol.37, No. 1)Publication Date: 2018-01-01
Authors : Muhammad Murtaza Yousaf Muhammad Umair Sadiq Laeeq Aslam Waqar ul Qounain Shahzad Sarwar;
Page : 223-232
Keywords : Edit Distance; Levenshtein Distance; OpenMP; Speedup;
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.
Other Latest Articles
- Planning Failure of Satellite Town: A Case Study of Korangi, Karachi-Pakistan
- Assessing the Effect of Different Water Table Depths on Water Use, Yield and Water Productivity of the Okra Crop
- Handwritten Sindhi Character Recognition Using Neural Networks
- Co-Relationship between California Bearing Ratio and Index Properties of Jamshoro Soil
- Investigating Multi-Array Antenna Signal Convergence using Wavelet Transform and Krylov Sequence
Last modified: 2018-02-04 03:17:08