最長共同遞增子序列問題之研究

A Study on the Longest Common Increasing Subsequence Problem

鄒翔宇(Hsiang-Yu Tsou)

指導教授 ： 王炳豐

國立清華大學/電機資訊學院/資訊工程學系/碩士(2012年)

摘要

本篇論文探討最長共同遞增子序列問題，並提出三個演算法。這三個演算法分別花費 O(rlg llglg σ + SortΣ(m))，O(r + nllglg σ + SortΣ(m)) 以及 O(ml + nllglg σ + SortΣ(m)) 的時間。其中 n 和 m 是兩條序列的長度 (m >= n)， r 是兩序列中相同字符的位置配對數量，l 是共同遞增子序列的長度， σ 是字符集 Σ 的大小，以及 SortΣ(m) 是將一個長度為 m 且在 Σ 字符集下的序列作排序所花費的時間。
目前在最長共同遞增子序列問題中最好的其中兩個演算法是由　Chan et al. 和 Brodal et al. 所提出。其時間複雜度分別為 O(rlg llglg n + SortΣ(m)) 和 O((m + nl)lglg σ + SortΣ(m))。基本上，本篇論文所提出的三個演算法是上面兩個演算法的簡單變形。第一個演算法改進 Chan et al. 的演算法，將其 lglg n 的乘數因子改進為 lglg σ 。而且，在某些情況下，本篇論文所提出的三個演算法會比Brodal et al. 提出的演算法還要好。

關鍵字

共同遞增子序列

並列摘要

無資料

並列關鍵字

Longest Common Increasing Subsequence ； Design and analysis of algorithms ； Common subsequences ； Increasing subsequences ； Van Emde Boas trees

參考文獻

[1] G. S. Brodal, K. Kaligosi, I. Katriel, and M. Kutz, "Faster algorithms for computing longest common increasing subsequences," in Proceedings of the 17th Annual Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science (2006), Vol. 4009, pp. 330–341.

[2] G. S. Brodal, K. Kaligosi, I. Katriel, and M. Kutz, "Faster algorithms for computing longest common increasing subsequences," Journal of Discrete Algorithms (2011), Vol. 9, No. 4, pp. 314–325.

[3] P. van Emde Boas, R. Kaas, and E. Zijlstra, "Design and implementation of an efficient priority queue," Mathematical Systems Theory (1977), Vol. 10, No. 1, pp. 99–127.

[4] S. Bespamyatnikh and M. Segal, "Enumerating longest increasing subsequences and patience sorting," Information Processing Letter (2000), Vol. 76, No. 1-2, pp. 7–11.

[5] M. Crochemore and E. Porat, "Fast computation of a longest increasing subsequence and application," Information and Computation (2010), Vol. 208, No. 9, pp. 1054–1059.