臺灣博碩士論文加值系統

最長共同子序列(The Longest Common Subsequence，LCS)的問題，就是針對二個序列A = A[1]…A[m]和B = B[1]…B[n]，其中m ≥ n，找出一序列C = C[1]…C[p]，使得C是A和B的最大長度共同子序列，最長共同子序列問題可以應用在許多地方，譬如訊號處理、圖形識別、資料壓縮、遺傳學、網路搜尋等，目前已有許多有效的演算法用來解決這一個問題；在各種不同的計算兩個序列最長共同子序列的長度和尋找最長共同子序列的演算法中，心跳式陣列演算法(systolic array algorithm)是最快的。在本論文中，我們提出心跳式陣列演算法使用n個處理元件(processing elements)，最長共同子序列的長度和最長共同子序列可以在(m + n + 1)個時間步驟求出，是目前我們所知需要最少個時間步驟即可求出最長共同子序列的心跳式陣列演算法，我們也使用Altera FPGA Stratix 晶片型號為EP1S10F484C5來實現，若m = n = 6時，其算出兩序列之共同子序列所需的操作時間為260ns，其總邏輯元素(total logic elements)使用率為7%，在10570個邏輯元素上使用了759個邏輯元素，邏輯元素的使用相當精簡，非常適合超大型積體電路的實現。

This paper implements a systolic array algorithm for computing longest common subsequence (LCS) problem. Given two strings of length m and n, m ?d n, the problem is defined as finding the longest common subsequence of the two input sequences. It has many applications, such as speech and signal processing, data compression, pattern recognition, string processing, and genetic engineering, and has been studied by many researchers. Our proposed systolic array algorithm uses n processing elements(PEs) and longest common subsequence can be obtained in (m + n + 1) time steps. If Altera FPGA Stratix EP1S10F484C5 is used, the operating time for finding the longest common subsequence of two strings with m = n = 6 is 260ns. The FPGA’s total logic elements utilization is 7% or 759 over 10,570 logic elements.

摘要i
ABSTRACTii
誌謝iii
目錄iv
表目錄v
圖目錄vi
第一章 緒論1
1.1 簡介1
1.2 最長共同子序列相關研究2
1.3 章節架構3
第二章 最長共同子序列4
2.1 計算最長共同子序列的長度4
2.2 計算最長共同子序列的長度之心跳式演算法5
2.3 計算最長共同子序列的長度實例7
2.4 計算最長共同子序列的長度之實現12
2.5 計算最長共同子序列16
2.6 新的心跳式陣列演算法16
2.7 計算最長共同子序列實例17
2.8 計算最長共同子序列之Verilog HDL程式23
2.9 計算最長共同子序列的實現27
第三章 快速的線性心跳式陣列結構31
3.1 處理元件的架構31
3.2 計算最長共同子序列34
3.3 線性心跳式陣列演算法35
3.4 計算最長共同子序列實例37
3.5 計算最長共同子序列之Verilog HDL程式41
3.6 計算最長共同子序列的實現48
3.7 改善後計算最長共同子序列的架構51
3.8 高效率的線性心跳式陣列演算法52
3.9 計算最長共同子序列實例53
3.10 改善後計算最長共同子序列之Verilog HDL程式57
3.11 改善後計算最長共同子序列的實現63
3.12 與其他演算法比較表66
第四章 結論67
參考文獻68

[1]吳其政，陳怡君，吳東旭，吳家榮，林永裁，「一個快速尋找最長共同子序列之心跳式演算法和硬體實現」，2009兩岸機電暨產學合作學術演討會，pp. 597-601，2009。
[2]吳其政，陳怡君，吳東旭，吳家榮，林永裁，「一個求最長共同子序列的高效率心跳式演算法及其FPGA實現」，2010ILT第五屆智慧生活科技研討會論文集，pp. 335-339，2010。
[3]A. Apostolico, M. Attalah, L. Larmore and S. Mcfaddin, “Efficient Parallel Algorithms for String Editing and Related Problems,” SIMA Journal on Computing, pp. 968-988, 1990.
[4]Y. Robert and M. Tchuente, “A systolic array for the longest common subsequence problem,” ICPP Inform, pp. 191-198, 1976.
[5]M. Crochemore, C.s. Iliopoulos, Y.J. Pinzon, and J.F. Reid, “A fast and practical bit-vector algorithm for the Longest Common Subsequence problem,” Inform Process Lett 80, pp. 279-285 ,2001.
[6]Y. C. Lin, “New systolic arrays for the longest subsequence problem,” Paral Comput 20, pp. 1323-1334, 1994.
[7]Thierry Lecroq, Guillaume Luce, Jean Frédéric Myoupo, “A faster linear systolic algorithm for recovering a longest common subsequence,” Information Processing Letters 61, pp. 129-136, 1995.
[8]W.J. Masek, M. Paterson, “A faster algorithm computing string edit distances,” Journal of Computer and System Sciences 20 (1), pp. 18-31, 1980.
[9]R.A. Wagner, M.J. Fischer, “The string-to-string correction problem,” Journal of the ACM 21(1), pp. 168-173, 1974.
[10]E.W. Myers, “An O(ND) difference algorithm and its variations,” Algorithmical (2) , pp. 251-266, 1986.
[11]N. Nakatsu, Y.Kambayashi, S. Yajima, “A longest common subsequence algorithm suitable for similar text strings,” Acta Informatica 18, 198, pp. 171-179, 1982.
[12]J.W. Hunt, T.G. Szymanski, “A fast algorithm for computing longest subsequences,” Communications of the ACM 20(5), pp. 350-353, 1977.
[13]M.S. Rahman, C.S. Iliopoulos, “A new efficient algorithm for computing the longest common subsequence,” Lecture Notes in Computer Science, vol. 4508, pp. 82-90, Springer, 2007.
[14]D.S. Hirschberg, “A linear space algorithm for computing maximal common subsequences,” Comm. ACM 18(6), pp. 341-343, 1975.