利用兩個Run-Length Encoded字串找出限制的最長共同子序列

Finding Constrained Longest Common Subsequences between Two Run-Length Encoded Strings

劉嘉翔(Chia-Hsiang Liu)

指導教授 ： 王有禮

國立暨南國際大學/科技學院/資訊工程學系/碩士(2008年)

摘要

在本文中主要探討利用兩個Run-length encoded的字串來解決限制的最長共同子序列(The constrained longest common subsequence，簡稱為CLCS)問題，CLCS是先給定兩個長度大於零的字串以及一個限制的字串，之後在兩個長度大於零的字串中找出包含限制字串的最長共同子序列。我們會介紹關於最長共同子序列(The longest common subsequence，簡稱為LCS)及限制的最長共同子序列(The constrained longest common subsequence，簡稱為CLCS)的相關論文與研究，也提出一個有效的演算法來解決CLCS的問題，並且會使用許多淺顯易懂的例子與圖表來解釋本篇論文最重要的想法，並且分析探討此演算法的證明與時間複雜度。

關鍵字

限制的最長共同子序列 ； 最長共同子序列 ； 行程長度編碼 ； 演算法

並列摘要

In this paper, we shall discuss how to solve the constrained longest common subsequence (CLCS) problem between two Run-length encoded strings. Given two run-length encoded strings X and Y and a constrained sequence P, a sequence Z is a constrained longest common subsequence for X and Y with respect to P if Z is a longest sequence of X and Y such that P is a subsequence of Z. We shall propose an efficient algorithm to solve the CLCS problem. The time complexity of our algorithm is O [ r (mN + Mn – mn) + S ], where string X has M characters and m runs, string Y has N characters and n runs and P has r characters and S are grids without calculating of Xi = Yj = Pk block.

並列關鍵字

CLCS ； LCS ； Run-length encoded ； Algorithms

參考文獻

[1] B. Alessandro, F. Valerio, Parallel Comparison of Run-Length-Encoded Strings on a Linear Systolic Array, Information Sciences 177 (2007) 231-238.

[2] A. Amir, A. Butman, M. Lewenstein, Real Scaled Matching, Information Processing Letters 70 (1999) 185–190.

[3] A. Apostolico, String Editing and Longest Common Subsequences, in: G. Rozenberg, A. Salomaa (Eds.), Linear Modeling: Background and Application, in: Handbook of Formal Languages, Vol. 2 (1997) 361–398.

[4] A. Apostolico, G. Landau, S. Skiena, Matching for Run-Length Encoded Strings, J. Complexity 15 (1) (1999) 4–16.

[5] O. Arbell, G.M. Landau, J.S.B. Mitchell, Edit Distance of Run Length Encoded Strings, Information Processing Letters 83 (2002) 307–314.