Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism |
| |
Authors: | Valerio Freschi |
| |
Affiliation: | STI, Università di Urbino, 61029 Urbino, Italy |
| |
Abstract: | Data compression can be used to simultaneously reduce memory, communication and computation requirements of string comparison. In this paper we address the problem of computing the length of the longest common subsequence (LCS) between run-length-encoded (RLE) strings. We exploit RLE both to reduce the complexity of LCS computation from O(M×N) to O(mN+Mn−mn), where M and N are the lengths of the original strings and m and n the number of runs in their RLE representation, and to improve the inherent parallelism of the proposed algorithm, so that it may execute in O(m+n) steps on a systolic array of M+N units.We also discuss the application of the proposed algorithm to the related problem of edit distance (ED) computation. |
| |
Keywords: | Algorithms Longest common subsequence Run-length encoding String comparison Parallel processing |
本文献已被 ScienceDirect 等数据库收录! |
|