# 臺灣博碩士論文加值系統

(34.204.181.91) 您好！臺灣時間：2023/10/01 14:12

:::

### 詳目顯示

:

• 被引用:0
• 點閱:97
• 評分:
• 下載:19
• 書目收藏:0
 在本論文中，我們首先定義了兩種基於融合最長共同子序列(MLCS)的變形問題，分別是融合最長共同子序列且子字串長度為t (MLCSt)問題和融合最長共同子序列且子字串長度大於等於t (MLCSt+)問題。這兩個問題討論了MLCS問題分別延伸至LCS問題且子字串長度為t (LCSt)和子字串長度大於等於t (LCSt+)。在本論文中，我們提出了動態規劃(DP)演算法來解決這兩種問題，時間複雜度為O(mnr)，其中m、n和r 分別為A、B和目標序列P的長度。在用於MLCSt+的DP演算法中，我們應用了Ueki等人的技術來降低時間複雜度。另外，我們將對角線概念應用於解決這兩種問題。基於對角線概念的MLCSt演算法的時間複雜度為O(R+(r-L+1)Lm)，MLCSt+演算法的時間複雜度為O(R+(r-L+1)(Lm+R))，其中R為A和P之間以及B和P之間的總配對數量，L是答案的長度。最後我們提出了一些實驗結果來說明我們算法的效率。
 In this thesis, we first defi ne two new variants of the merged longest commonsubsequence (MLCS) problem. They are the MLCS problem with t-length substrings(MLCSt) and the MLCS problem with at least t-length substrings (MLCSt+). TheMLCSt and MLCSt+ problems discuss the merged LCS (MLCS) extended from theLCS problems with t-length substrings (LCSt) and with at least t-length substrings(LCSt+), respectively. In this thesis, we propose the dynamic programming (DP)algorithms for solving these two problems in O(mnr) time, where m, n and r are thelengths of the two main sequences A and B and the target sequence P, respectively.In the DP algorithm for MLCSt+, we apply the technique of Ueki et al. to reduce thetime complexity. In addition, we apply the diagonal concept to the solving of thesetwo problem. The time complexity of the diagonal algorithms for solving the MLCStproblem is O(R + (r -L + 1)Lm) and for MLCSt+ is O(R + (r -L + 1)(Lm + R)),where R is the number of total match pairs between A and P, and between B andP, L is the length of the answer. We also present some experimental results toillustrate the e fficiency of our algorithms.
 THESIS VERIFICATION FORM . . . . . . . . . . . . . . . . . . . . . . iTHESIS AUTHORIZATION FORM . . . . . . . . . . . . . . . . . . . . iiiACKNOWLEDGEMENT . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiCHINESE ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vLIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiLIST OF SYMBOLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiChapter 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1Chapter 2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.1 The Merged Longest Common Subsequence Problem . . . . . . . . . 52.2 The Diagonal Algorithm for Solving the MLCS Problem by Tseng et al. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.3 The Longest Common Subsequence Problem with t-length Substrings (LCSt) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.4 The Longest Common Subsequence Problem with at Least t-length Substrings (LCSt+) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.5 The De nitions of the MLCSt and MLCSt+ Problems . . . . . . . . . 12Chapter 3. The Algorithms for the MLCSt and MLCSt+ Problems . 153.1 The Dynamic Programming Algorithms for MCSt and MLCSt+ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.2 The Diagonal Algorithm for MLCSt . . . . . . . . . . . . . . . . . . . 263.3 The Diagonal Algorithm for MLCSt+ . . . . . . . . . . . . . . . . . . 32Chapter 4. Experimental Results . . . . . . . . . . . . . . . . . . . . . . 424.1 The Merged Longest Common Subsequence Problem with t-Length Substrings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.2 The Merged Longest Common Subsequence Problem with at least t-Length Substrings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.3 Brief Summary for the Experimental Results . . . . . . . . . . . . . . 52Chapter 5. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54AppendixesA. The Additional Experimental Results of MLCSt . . . . . . . . . . . 57B. The Additional Experimental Results of MLCSt+ . . . . . . . . . . 70
 [1] H. Y. Ann, C. B. Yang, C. T. Tseng, and C. Y. Hor, "Fast algorithms forcomputing the constrained LCS of run-length encoded strings," TheoreticalComputer Science, Vol. 432, pp. 1-9, 2012.[2] A. N. Arslan and o. E gecio glu, "Algorithms for the constrained longest commonsubsequence problems," International Journal of Foundations of ComputerScience, Vol. 16, pp. 1099-1109, 2005.[3] G. Benson, A. Levy, S. Maimoni, D. Noifeld, and B. R. Shalom, "LCSk: Are ned similarity measure," Theoretical Computer Science, Vol. 638, pp. 11-26, 2016.[4] G. Benson, A. Levy, and B. R. Shalom, "Longest common subsequence in klength substrings," Proceedings of the 6th International Conference on Similar-ity Search and Applications, Vol. 8199, pp. 257-265, 2013.[5] Y. C. Chen and K. M. Chao, "On the generalized constrained longest commonsubsequence problems," Journal of Combinatorial Optimization, Vol. 21, pp. 283-392, 2011.[6] F. Y. L. Chin, A. D. Santis, A. L. Ferrara, N. L. Ho, and S. K. Kim, "A simplealgorithm for the constrained sequence problems," Information Processing Letters, Vol. 90, pp. 175-179, 2004.[7] S. Deorowicz, "Bit-parallel algorithm for the constrained longest common subsequenceproblem," Fundamenta Informaticae, Vol. 99, pp. 409-433, 2010.[8] S. Deorowicz and A. Danek, "Bit-parallel algorithms for the merged longestcommon subsequence problem," International Journal of Foundations of Computer Science, Vol. 24, pp. 1281-1298, 2013.[9] S. Deorowicz and S. Grabowski, "E cient algorithms for the longest commonsubsequence in k-length substrings," Information Processing Letters, Vol. 114, pp. 634-638, 2014.[10] Z. Gotthilf, D. Hermelin, and M. Lewenstein, "Constrained LCS: Hardness andapproximation," Proceedings of the 19th Annual Symposium on CombinatorialPattern Matching (CPM), Vol. 5029, Pisa, Italy, pp. 255-262, 2008.[11] S. Grabowski, "New tabulation and sparse dynamic programming basedtechniques for sequence similarity problems," Discrete Applied Mathematics, Vol. 201, pp. 96-103, 2016.[12] G. F. Huang, C. B. Yang, K. T. Tseng, and K. S. Huang, "Diagonal algorithmsfor the longest common subsequence problems with t-length and atleast t-length substrings," Proceedings of the 37th Workshop on CombinatorialMathematics and Computation Theory, Kaohsiung, Taiwan, pp. 119-127, 2020.[13] K. S. Huang, C. B. Yang, K. T. Tseng, H. Y. Ann, and Y. H. Peng, "E cient algorithmsfor nding interleaving relationship between sequences," InformationProcessing Letters, Vol. 105, pp. 188-193, 2008.[14] S. H. Hung, C. B. Yang, and K. S. Huang, "A diagonal-based algorithm for theconstrained longest common subsequence problem," Proceedings of the 23rd In-ternational Computer Symposium 2018 (ICS 2018), Vol. 1013, Yunlin, Taiwan, pp. 425-432, 2018.[15] N. Nakatsu, Y. Kambayashi, and S. Yajima, "A longest common subsequencealgorithm suitable for similar text strings," Acta Informatica, Vol. 18, pp. 171-179, 1982.[16] F. Paveti c, I. Katani c, G. Matula, G. Zu zi c, and M. Siki c, "Fast and simplealgorithms for computing both LCSk and LCSk+," CoRR, abs/1705.07279, 2018.[17] F. Paveti c, G. Zu zi c, and M. Siki c, "LCSk++: Practical similarity metric forlong strings," CoRR, abs/1407.2407, 2014.[18] Y. H. Peng, C. B. Yang, C. T. Tseng, and K. S. Huang, "An algorithm andapplications to sequence alignment with weighted constraint," InternationalJournal of Foundations of Computer Science, Vol. 21, pp. 51-59, 2010.[19] Y. H. Peng, C. B. Yang, K. S. Huang, C. T. Tseng, and C. Y. Hor, "E -cient sparse dynamic programming for the merged LCS problem with blockconstraints," International Journal of Innovative Computing, Information andControl, Vol. 6, pp. 1935-1947, 2010.[20] A. M. Rahman and M. S. Rahman, "E ective sparse dynamic programmingalgorithms for merged and block merged LCS problems," Journal of Computers, Vol. 9(8), pp. 1743-1754, 2014.[21] Y. T. Tsai, "The constrained longest common subsequence problem," Information Processing Letters, Vol. 88, pp. 173-176, 2003.[22] C. T. Tseng, C. B. Yang, and H. Y. Ann, "E cient algorithms for the longestcommon subsequence problem with sequential substring constraints," Journalof Complexity, Vol. 29(1), pp. 44-52, 2013.[23] K. T. Tseng, D. S. Chan, C. B. Yang, and S. F. Lo, "E cient merged longestcommon subsequence algorithms for similar sequences," Theoretical Computer Science, Vol. 708, pp. 75-90, 2018.[24] Y. Ueki, Diptarama, M. Kurihara, Y. Matsuoka, K. Narisawa, R. Yoshinaka,H. Bannai, S. Inenaga, and A. Shinohara, "Longest common subsequence inat least k length order-isomorphic substrings," Proceedings of the 43rd Inter-national Conference on Current Trends in Theory and Practice of ComputerScience, Vol. 10139, Limerick, Ireland, pp. 364-374, 2017.[25] R. A. Wagner and M. J. Fischer, "The string-to-string correction problem,"Journal of the ACM, Vol. 21(1), pp. 168-173, 1974.[26] D. Zhu, L. Wang, T. Wang, , and X. Wang, "A space e cient algorithm forthe longest common subsequence in k-length substrings," Theoretical ComputerScience, Vol. 687, pp. 79-92, 2017.[27] D. Zhu, L. Wang, T. Wang, and X. Wang, "A simple linear space algorithm forcomputing a longest common increasing subsequence," IAENG InternationalJournal of Computer Science, Vol. 45(3), pp. 472-477, 2018.
 電子全文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 另一個解決嵌合式最長共同子序列問題的演算法 2 基於動態規劃與狀態機之形狀辨識研究 3 求最長共同子序列之硬體架構IP設計與驗證 4 自動化歌曲分段和主副歌辨識 5 附加條件限制之最長共同子序列方法 6 最長共同子序列且子字串長度為t與大於等於t問題之對角線演算法 7 最長共同回文子序列問題之對角線演算法 8 最長共同遞增子序列問題之對角線演算法 9 限制最長共同子序列之對角線演算法 10 小字符集的限制最長共同子序列之快速演算法 11 編輯距離問題與相關問題演算法之回顧 12 彈性最長共同子序列問題之演算法 13 在GPU中使用CUDA去加速最長共同子序列演算法 14 具間隙型限制的最長共同子序列問題 15 三序列之最長共同子序列問題

 無相關期刊

 1 重建胺基酸評分矩陣以改善固有無序蛋白質的同源性檢測 2 以文風指標分析《紅樓夢》的作者爭議問題 3 應用重啟隨機遊走的miRNA與疾病關聯性之預測方法 4 使用回文分解進行非重疊反轉之序列比對演算法 5 最長共同子序列且子字串長度為t與大於等於t問題之對角線演算法 6 最長共同平方子序列問題之有效率演算法 7 基於卷積神經網路的台灣股市之投資組合交易 8 一個有效的半監督式學習方法應用於入侵偵測系統 9 奢華都是為了愛你！求偶思維對不同類型奢侈性消費之影響 10 播進「擬」的心：以社會支持觀點探討直播購物對觀眾的消費意圖 11 以聚麩胺酸加強生物復育受三氯乙烯污染場址： 基質開發及效益評估 12 電力系統雙重支配集問題的分支分解動態規劃演算法 13 基於生成對抗網路之錯誤影像修復方法之全面分析 14 適用於深度學習之稀有訓練資料自動擴展方法研究：以交通標誌偵測為例 15 應用資訊檢索提取網路威脅情資

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室