請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/63190| 標題: | 多壓縮字串之最長共同子序列計算 Computing the Longest Common Subsequence of Multiple RLE Strings |
| 作者: | Ling-Chih Yao 姚甯之 |
| 指導教授: | 趙坤茂 |
| 關鍵字: | 多壓縮字串,最長共同子序列,未解壓縮,動態規劃法,範圍樹, Compressed strings,Longest Common Subsequence,Bypassing the decompression, |
| 出版年 : | 2012 |
| 學位: | 碩士 |
| 摘要: | 本論文探討給定多個(三條以上)壓縮字串(multiple RLE strings)，在其未解壓縮的情況下，直接以壓縮過後的資訊去計算最長共同子序列(Longest Common Subsequence)。我們總共闡述了三個演算法。第一個演算法，藉由觀察其計算特性，提出三個定理(lemmas)，並由動態規劃法(dynamic programming)方式呈現我們的演算法。第二個演算法，藉由字串相似區段(matched blocks)數量的異同，進一步加速我們的演算法。第三個演算法，利用資料結構範圍樹(range trees)進一步加速尋找標的的速度，進而加快我們的計算。 |
| URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/63190 |
| 全文授權: | 有償授權 |
| 顯示於系所單位： | 資訊網路與多媒體研究所 |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-101-1.pdf 目前未授權公開取用 | 438.38 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。