多壓縮字串之最長共同子序列計算

Abstract

本論文探討給定多個(三條以上)壓縮字串(multiple RLE strings)，在其未解壓縮的情況下，直接以壓縮過後的資訊去計算最長共同子序列(Longest Common Subsequence)。我們總共闡述了三個演算法。第一個演算法，藉由觀察其計算特性，提出三個定理(lemmas)，並由動態規劃法(dynamic programming)方式呈現我們的演算法。第二個演算法，藉由字串相似區段(matched blocks)數量的異同，進一步加速我們的演算法。第三個演算法，利用資料結構範圍樹(range trees)進一步加速尋找標的的速度，進而加快我們的計算。