碩論：最長共同近乎波動子序列問題 2 ｜The Longest Common Almost Wave Subsequence Problem (LCaWS)

這篇介紹我的碩論：最長共同近乎波動子序列問題 (LCaWS)，波動序列問題如何發展？LCaWS如何應用於即時監測心律異常？如何有效率解決LCaWS問題？未來可以如何改善LCaWS演算法？

文章連結

  1. 碩論：最長共同近乎波動子序列問題 1
    1. 主要貢獻
    2. 摘要
    3. 問題簡介與應用
    4. LCaWS演算法概念
    5. LCaWSt演算法
  2. 碩論：最長共同近乎波動子序列問題 2
    1. LCaWSr演算法
    2. 結論


（三）LCaWSr 問題與演算法

LCaWSr 問題則要找出兩條序列 A 與 B 的最長共同波動子序列，其序列最多由 r 段近乎遞增與遞減段交替組成。

LCaWSr問題範例

A = <3, 2, 7, 4, 5, 2, 8>、B = <3, 8, 2, 7, 4, 5, 2>、r = 3和c = 3，則LCWSr = <3, 2, 7, 5, 2>、LCaWSr＋ = <3, 2, 7, 4, 5, 2>和LCaWSr− = <3, 2, 7, 4, 5, 2>。這裡的紅色實線代表近乎遞增段，藍色虛線代表近乎遞減段。

我們使用L表與β表去解決LCaWSr問題，L表和β表每一格都是記錄2元組<base, len>的集合。我們不失普遍性地假設第一段為近乎遞增段，也就是第奇數段為近乎遞增，而第偶數段為近乎遞減。

  • 如果k為奇數，則L(i, j, k)中每個2元組的len為A1..i和B1..j的LCaWSr長度，其最後一個元素為bj且第k段為近乎遞增段，而base則為第k段的最大值。
  • 如果k為偶數，則L(i, j, k)是記錄近乎遞減段的長度與最小值。
  • 如果k為奇數，則β(i, j, k)會從L(i-1, j, k)中收集未來接上ai會形成近乎遞增段的2元組，同時也會繼承β(i, j-1, k)所有2元組。
  • 如果k為偶數，則β(i, j, k) 收集未來會形成近乎遞減段的2元組。

因此，β表會收集未來有潛力的2元組，為了更好理解LCaWSr演算法，以下使用L表的虛線藍框框代表未來有潛力的2元組（β）。接下來，我們以開頭為近乎遞增段的部分來解釋我們LCaWSr演算法。

第一回（a1 = 3）：

  • 我們會得到<3>這個長度為1的答案，因為a1 = b1 = 3，因此L(1, 1, k) = {<3,1>}。
  • 如果k為奇數，則3是在近乎遞增的第k段的最大值且其長度為1。
  • 如果k為偶數，則3是在近乎遞減的第k段的最小值且其長度為1。

第二回（a2 = 2）：

  • k = 1：<3,1> ∈ L(1, 1, 1) 是可以接上2的近乎遞增潛力解，因此 L(2, 3, 1) = {<2,1>, <3,2>}，其可能解為{<2>, <3-2>}。
  • k = 2：<3,1> ∈ L(1, 1, 2) 是可以接上2的近乎遞減潛力解，因此 L(2, 3, 2) = {<2,2>}。同時可以把第1段末視為轉折點，所以 L(2, 3, 2) 可以繼承 L(2, 3, 1)，因此 <2,2> ∈ L(2, 3, 2) 可能解為<3-2> 或 <3-2>，前者是延伸 L(1, 1, 2)；後者是繼承 L(2, 3, 1)。
  • k = 3：<3,1> ∈ L(1, 1, 3) 是可以接上2的近乎遞增潛力解，因此 <3,2> ∈ L(2, 3, 3)。同時可以把第2段末視為轉折點，所以 L(2, 3, 3) 可以繼承 L(2, 3, 2)，因此 <2,2> ∈ L(2, 3, 3)。故 L(2, 3, 3) = {<2,2>, <3,2>}，其可能解為{<3-2>, <3-2>}，前者是延伸 L(1, 1, 3)；後者是繼承 L(2, 3, 2)。

第三回（a3 = 7）：

  • k = 1：<3,2> ∈ L(2, 3, 1) 是可以接上7的近乎遞增潛力解，因此 L(3, 4, 1) = {<7,3>}，其可能解為{<3-2-7>}。
  • k = 2：雖然沒有任何可以接上7的近乎遞減潛力解，但可以把第1段末視為轉折點，所以 L(3, 4, 2) 可以繼承 L(3, 4, 1)，因此 L(3, 4, 2) = {<7,3>}，其可能解為<3-2-7>。
  • k = 3：<2,2> ∈ L(2, 3, 3) 是可以接上7的近乎遞增潛力解，同時可以把第2段末視為轉折點，所以 L(3, 4, 3) 可以繼承 L(3, 4, 2)，因此 L(3, 4, 3) = {<7, 3>}，其可能解為 <3-2-7> 或 <3-2-7>，前者是延伸 L(2, 3, 3)；後者是繼承 L(3, 4, 2)。

第四回（a4 = 4）：

  • k = 1：<3,2> ∈ L(3, 3, 1) 是可以接上4的近乎遞增潛力解，因此 L(4, 5, 1) = {<4,3>}，其可能解為{<3-2-4>}。注意<7,3> ∈ L(3, 4, 1)不是近乎遞增潛力解，因為不許7後面接4。 
  • k = 2：<7,3> ∈ L(3, 4, 2) & <3,1> ∈ L(3, 1, 2) & <2,2> ∈ L(3, 3, 2) 是可以接上4的近乎遞減潛力解，因此 L(4, 5, 2) = {<4,4>, <3,2>, <2,3>}，其可能解為{<3-2-7-4>, <3-4>, <3-2-4>}。
  • k = 3：可以把第2段末視為轉折點，所以 L(4, 5, 3) 可以繼承 L(4, 5, 2)，因此 L(4, 5, 3) = {<4, 4>}，其可能解為<3-2-7-4>。

第五回（a5 = 5）：

  • k = 1：<4,3> ∈ L(4, 5, 1) & <7,3> ∈ L(4, 4, 1) 是可以接上5的近乎遞增潛力解，因此 L(5, 6, 1) = {<5,4>, <7,4>}，其可能解為{<3-2-4-5>, <3-2-7-5>}。
  • k = 2：<7,3> ∈ L(4, 4, 2) & <4,4>, <3,2> ∈ L(4, 5, 2) 是可以接上5的近乎遞減潛力解，同時可以把第1段末視為轉折點，所以 L(5, 6, 2) 可以繼承 L(5, 6, 1)，因此 L(5, 6, 2) = {<5,4>, <4,5>, <3,3>}，其可能解為{<3-2-4-5>, <3-2-7-4-5>, <3-4-5>}。注意<2,3> ∈ L(4, 5, 2) 不是近乎遞減潛力解，因為不允許2後面接5。
  • k = 3：<4,4> ∈ L(3, 4, 3) & <7,3> ∈ L(4, 4, 3) 是可以接上5的近乎遞增潛力解，同時可以把第2段末視為轉折點，所以 L(5, 6, 3) 可以繼承 L(5, 6, 2)，因此 L(5, 6, 3) = {<5,5>, <7,4>}，其可能解為{<3-2-7-4-5>, <3-2-7-5>}。

第六回（a6 = 2）：

  • k = 1：<2,1>, <3,2> ∈ L(5, 3, 1) & <4,3> ∈ L(5, 5, 1) 是可以接上2的近乎遞增潛力解，因此 L(6, 7, 1) = {<2,2>, <3,3>, <4,4>}，其可能解為{<2-2>, <3-2-2>, <3-2-4-2>}。
  • k = 2：<4,5> ∈ L(5, 6, 2) 是可以接上2的近乎遞減潛力解，因此 L(6, 7, 2) = {<2,6>}，其可能解為{<3-2-7-4-5-2>}。
  • k = 3：<2,2>, <3,2> ∈ L(5, 3, 3) & <4,4> ∈ L(5, 5, 3) 是可以接上2的近乎遞增潛力解，同時可以把第2段末視為轉折點，所以 L(6, 7, 3) 可以繼承 L(6, 7, 2)，因此 L(6, 7, 3) = {<2,6>, <3,3>, <4,5>}，其可能解為{<3-2-7-4-5-2>, <3-2-2>, <3-2-7-4-2>}。

其餘部分也用相似方式去更新，最後我們會得到長度為6的LCaWSr＋，因為<2,6>是在L(7, j, k)中有最大的長度。除了長度，我們可以使用L表追溯出LCaWSr＋為<3-2-7-4-5-2>，因為<2,6> ∈ L(6, 7, 2)、<4,5> ∈ L(5, 6, 2)、<4,4> ∈ L(4, 5, 2)、<7,3> ∈ L(3, 4, 2 & 1)、<3,2> ∈ L(2, 3, 1)和<3,1> ∈ L(1, 1, 1)是關鍵的2元組。為了得到最終的LCaWSr答案，我們也需要得到開頭為近乎遞減段的LCaWSr− = <3-2-7-4-5-2>。

我們將LCaWSr＋和LCaWSr−視覺化，可以得知LCaWSr＋的第一段<3-2-7>為近乎遞增段且第二段<7-4-5-2>為近乎遞減段，而LCaWSr−的第一段<3-2>為近乎遞減段，第二段<2-7>為近乎遞增段且第三段<7-4-5-2>為近乎遞減段。LCaWSr＋和LCaWSr−長度一樣且段數皆小於等於r = 3，因此兩者皆為我們最終的LCaWSr答案。


五、結論

（一）時間複雜度

我們正式定義LCaWS問題並提出相對應的演算法，LCaWS問題包含LCaWSt和LCaWSr問題。我們的LCaWSt演算法需要O(mnc)時間與O(nc)空間；而LCWSr演算法需要O(rmnc)時間與O(rnc)空間，其中m與n為兩條給定的序列長度，r為段數，c為公差。

我們的LCaWS演算法時間複雜度比Chang和Yang的LCWS演算法[CY21]多出O(c)的時間，且Bhuiyan等人的LCaIS演算法[BAR22]時間複雜度也和O(c)有關，但Lin的LaWS演算法[Lin22]時間與Chen和Yang的LWS演算法時間複雜度[CY20]卻幾乎一樣。因此雖然LaWS和LWS演算法時間複雜度幾乎一樣，但LCaWS演算法受限於LCaIS演算法的時間複雜度，所以LCaWS演算法時間複雜度目前無法把O(c)拿掉。

（二）演算法改善

雖然要從LCaWS演算法時間複雜度中拿掉O(c)也許是困難的，但我們未來可以開發出在某些情況中比較快的演算法。例如：Lo等人[LTY+20]應用對角線方法於LCIS問題上，其對角線方法在答案序列較小或較大時較快。Bhuiyan等人[BAR22]除了提出O(mnc)時間的LCaIS演算法外，還有提出另一個以匹配數為主的演算法，其方法在匹配數較小時較快。故未來可以借鏡以上兩種方法來改善LCaWS演算法的執行時間。


資助

這項研究工作得到台灣國家科學技術委員會根據合約 MOST 111-2221-E-110-034 的部分支持。


相關文章

  1. 跨科仔準備與分析中山資工所的過程
  2. 中山資工所 找教授｜柯正雯、楊昌彪、程正傑
  3. 從生科轉資工的初期過程｜十個問答
  4. 生科轉資工1：一年表現狀況
  5. 生科轉資工2：二年表現狀況1
  6. 生科轉資工2：二年表現狀況2
  7. 碩論：最長共同近乎波動子序列問題 1
  8. 碩論：最長共同近乎波動子序列問題 2
  9. 生科轉資工3：入職趨勢一週年1
  10. 生科轉資工3：入職趨勢一週年2


參考資料

  1. 呂宗霖。2023年。最長共同近乎波動子序列問題。臺灣碩博士論文知識加值系統
  2. Lu, Tsung-Lin, Kuo-Si Huang, and Chang-Biau Yang. "An Algorithm for Finding the Longest Common Almost Wave Subsequence with the Trend." 2023 14th IIAI International Congress on Advanced Applied Informatics (IIAI-AAI). IEEE, 2023.
  3. 演算法與計算理論學會。2024年。2023年最佳碩士論文優等獎：最長共同近乎波動子序列問題


引用文獻

  1. [1] M. R. Alam and M. S. Rahman, "A divide and conquer approach and a work-optimal parallel algorithm for the lis problem," Information Processing Letters, Vol. 113, No. 13, pp. 470-476, 2013.
  2. [2] S. Bespamyatnikh and M. Segal, "Enumerating longest increasing subsequences and patience sorting," Information Processing Letters, Vol. 76, No. 1-2, pp. 7-11, 2000.
  3. [3] M. T. H. Bhuiyan, M. R. Alam, and M. S. Rahman, "Computing the longest common almost-increasing subsequence," Theoretical Computer Science, Vol. 930, pp. 157-178, 2022.
  4. [4] Y.-C. Chang and C.-B. Yang, "The longest common wave subsequence problem," The 38th Workshop on Combinatorial Mathematics and Computation Theory, Taipei, Taiwan, pp. 9-17, 2021.
  5. [5] G.-Z. Chen and C.-B. Yang, "The longest wave subsequence problem: Generalizations of the longest increasing subsequence problem," The 37th Workshop on Combinatorial Mathematics and Computation Theory, Kaohsiung, Taiwan, pp. 28-33, 2020.
  6. [6] M. Crochemore and E. Porat, "Fast computation of a longest increasing subsequence and application," Information and Computation, Vol. 208, No. 9, pp. 1054-1059, 2010.
  7. [7] A. L. Delcher, S. Kasif, R. D. Fleischmann, J. Peterson, O. White, and S. L. Salzberg, "Alignment of whole genomes," Nucleic Acids Research, Vol. 27, No. 11, pp. 2369-2376, 1999.
  8. [8] A. Elmasry, "The longest almost-increasing subsequence," Information Processing Letters, Vol. 110, No. 16, pp. 655-658, 2010.
  9. [9] J. W. Hunt and T. G. Szymanski, "A fast algorithm for computing longest common subsequences," Communications of the ACM, Vol. 20, pp. 350-353, 1977.
  10. [10] A. Khelassi1, S.-N. Yelles-Chaouche, and F. Benais, "Multi-arrhythmias detection with an XML rule-based system from 12-Lead Electrocardiogram," Electronic Physician, Vol. 9, pp. 4357-4363, 2017.
  11. [11] S.-C. Lin, "The longest almost wave subsequence problem," Master''s Thesis, Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan, 2022.
  12. [12] S.-F. Lo, K.-T. Tseng, C.-B. Yang, and K.-S. Huang, "A diagonal-based algorithm for the longest common increasing subsequence problem," Theoretical Computer Science, Vol. 815, pp. 69-78, 2020.
  13. [13] J. M. Moosa, M. S. Rahman, and F. T. Zohora, "Computing a longest common subsequence that is almost increasing on sequences having no repeated elements," Journal of Discrete Algorithms, Vol. 20, pp. 12-20, 2013.
  14. [14] C. Schensted, "Longest increasing and decreasing subsequences," Canadian Journal of Mathematics, Vol. 13, pp. 179-191, 1961.
  15. [15] T. T. Ta, Y.-K. Shieh, and C. L. Lu, "Computing a longest common almost-increasing subsequence of two sequences," Theoretical Computer Science, Vol. 854, pp. 44-51, 2021.
  16. [16] P. van Emde Boas, R. Kaas, and E. Zijlstra, "Design and implementation of an efficient priority queue," Mathematical Systems Theory, Vol. 10, No. 1, pp. 99-127, 1976.
  17. [17] I.-H. Yang, C.-P. Huang, and K.-M. Chao, "A fast algorithm for computing a longest common increasing subsequence," Information Processing Letters, Vol. 93, No. 5, pp. 249-253, 2005.

留言

張貼留言