oai:pc01.lib.ntust.edu.tw:1793:etd-1212106-164354 資訊

本論文已被瀏覽 18 次， [ 造訪詳細資料與全文 ] 0 次，[ 回到前頁查詢結果 ] [ 重新搜尋 ]

解決最長共同子序列問題的可實作且有效率心跳式演算法之研究

An lmplementable and Efficient Systolic Algorithm for the Longest Common Subsequence Problem

作者：王琮偉
畢業學校：國立臺灣科技大學
出版單位：國立臺灣科技大學
核准日期：2006-12-13
類型：Electronic Thesis or Dissertation
權限：Copyright information available at source archive--National Taiwan University of Science and Technology....

中文摘要

最長共同子序列(longest common subsequence)問題是用來尋找兩個字串的最長共同子序列，它應用在很多不同的領域當中，諸如語音及信號處理(speech and signal processing)、資料壓縮(data compression)、圖形辨識(syntactic pattern recognition)、字元處理(string processing)以及遺傳工程學 (genetic engineering)等。
其輸入的兩個字串的長度都相當長，因此所需的處理時間相當久。有很多演算法被研究出來以降低處理時間，先前心跳式演算法雖然只用線性個處理單元就可達到線性時間複雜度，但是每個處理單元需要線性記憶體空間儲存中間結果，整體所需記憶體空間太大，並不適合實作於VLSI。因此設計一個既可實作於VLSI上又可加速處理速度的演算法，將是重要課題。
本論文旨在提出一個既可實作且有效率的心跳式演算法以解決最長共同子序列問題。首先研究重疊等高線的特性，使用“分而擊破”法從重疊等高線中找出最長共同子序列，整體只需線性記憶體空間，且只增加少許時間複雜度。並運用虛擬處理單元之概念，其實體處理單元的數目可固定，因此本心跳式演算法可實作於VLSI上，以加速處理速度。

英文摘要

The problem of longest common subsequence is defined to be finding the longest common subsequence of two input sequences. It can be employed in many fields such as speech and signal processing, data compression, syntactic pattern recognition, string processing, and genetic engineering.
Usually, lengths of both input sequences are very long, resulting in long processing time. Many previous algorithms have been proposed to reduce the processing time. Previous systolic algorithms can achieve linear time complexity with linear number of processing elements. However, each processing element needs linear memory space to store intermediate results and then the system needs too large memory space in total, resulting in not suitable for being implemented on VLSI. Hence, to design an implementable and efficient algorithm is an important issue.
The purpose of this thesis is to propose an implementable and efficient systolic algorithm for the longest common subsequence problem. At first, we investigate the property of overlapped contours. By employing divide and conquer technique, we can find a longest common subsequence from the overlapped-contours. It needs a little more time complexity with only linear memory space. Furthermore, the number of physical processing elements can be fixed by employing the concept of virtual processing elements. Therefore, our proposed systolic algorithm is not only implementable on VLSI but also efficient.

[1] A. Apostolico, and Z. Galil (eds), “Pattern Matching Algorithms,” Oxford University Press, 1997.
[2] C. Crochemore, and W. Rytter, “Text Algorithm,” Oxford University Press, 1994.
[3] G. A. Stephen, “String Searching Algorithm,” World Scientific, 1994.
[4] D. Gusfield, “Algorithms on Strings, Tree and Sequences,” Cambridge University Press, New York, 1997.
[5] E. W. Myers, “AnOverview of Sequence Comparison Algorithms in Molecular Biology,” Technical Report, TR 9129, Dept. of CS, The University of Arizona, Tucson, Arizona.
[6] D. Sankoff and J.B. KrusKal (eds), “Time Warps, String Edits, and Macromolecule: The Theory and Practice of Sequence Comparison,” Addison-Wesley, 1983.
[7] W.R. Pearson and D. J. Lipman, “Improved Tools for Biological Sequence Comparison,” in Proc. Natl. Acad. Sci. USA, Vol. 85, April 1988, pp. 2444-2448.
[8] S.F. Altschul, W. Gish, W. Miller, W. Myers, E. W and D. J. Lipman, “Basic Local Alignment Search Tool,” J. Mol. Biol., Vol. 215, 1990, pp. 403-410.
[9] X. Tang, R. Tian, and D. F. Wong, “Fast Evaluation of Sequence Pair in Block Placement by Longest Common Subsequence Computation,” IEEE Transactions Vol. 20, no. 12, Dec. 2001, pp. 1406-1413.
[10] X. Tang and M.D.F. Wong, “On Handling Arbitrary Rectilinear Shape Constraint,” Design Automation Conference, 2004. Proceedings of the ASP-DAC 2004. Asia and South Pacific 27-30 Jan. 2004, pp. 38-41.
[11] M. Vlachos, D. Gunopulos, and G. Kollios, “Robust Similarity Measures for Mobile Object Trajectories,” Database and Expert Systems Applications, 2002. vol. 13, Sept. 2002 pp. 721-726.
[12] H. Fashandi and A. M. Eftekhari Moghaddam, “A New Rotation Invariant Similarity Measure for Trajectories,” Computational Intelligence in Robotics and Automation, 2005. CIRA 2005. Proceedings. 2005 IEEE International Symposium on 27-30, June 2005, pp. 631-634.
[13] A. Aho, D. Hirschberg, and J. D. Ullman, “Bounds on the Complexity of the Longest Common Subsequence Problem,” Journal of the ACM. 23, 1 (1976), 1-12.
[14] M. Du and W. Hsu, “New Algorithms for the Longest Common Subsequence Problem,” Journal of Computer and System Siences 29 (1984), 133-152.
[15] D. S. Hirschberg, “Algorithms for the Longest Common Subsequence Problem,” Journal of the ACM (1977) 24(4), pp. 664-675.
[16] J. W. Hunt and T. G. Szymanski, “A Fast Algorithm for Computing Longest Common Subsequences,” Communication of the ACM (1977) 18, pp. 350-353.
[17] Y. Kayambayashi, N .Nakatsu and S. Yajima, “A Longest Algorithm Suitable for Similar Text String,” Acta Informatica (1982) 18, pp. 171-179.
[18] W. J. Masek and M. S. Paterson, “A Fast Algorithm for Computing String Edit Distances,” Journal of Computer and System Science (1998) 20, pp. 18-31.
[19] L. Bergroth, H. Hakonen, and T. Raita, “A Survey of Longest Common Subsequences Algorithms,” String Processing and Information Retrieval, 2000. SPIRE 2000. Proc. Vol. 7, Sept. 2000, pp. 39-48.
[20] A. Apostolico, S. Browne, and C. Guerra, “Fast Linear-Space Computations of Longest Common Subsequences,” Theor. Comp. Sc., 1992, pp. 3-17.
[21] A. Apostolico and C. Guerra, “A Fast Linear Space Algorithm Computing Longest Common Subsequences,” Proc. Of the 23rd Allerton Conf., Monticello, IL, 1985, pp. 76-84.
[22] D. S. Hirschberg, “A Linear Space Algorithm for Computing Maximum Common Subsequences,” Comm. Of the ACM, vol. 18, no. 6, 1975, pp. 341-343
[23] S. K. Kumar and C. P. Rangan, “A Linear-Space Algorithms for the LCS problem,” Acta Informatica, vol. 24, 1987, pp. 353-362.
[24] A. Apostolico, M. Attalah, L. Larmore and S. Mcfaddin, “Efficient Parallel Algorithms for String Editing and Related Problems,” SIMA Journal on Computing (1990) 19, pp. 968-988.
[25] M. Lu and H. Lin, “Parallel Algorithms for the Longest Common Subsequence Problem,” IEEE Transactions, vol. 5, no. 8, Aug. 1994, pp. 835-848
[26] T. Garcia, J. F. Myoupo and D. Seme, “A Work-Optimal CGM Algorithm for the Longest Increasing Subsequence Problem,” International Conference n Parallel and Distributed Processing Techniques and Applications (PDPTA’01), (2001)
[27] T. Garcia, J. F. Myoupo, and D. Seme, “A coarse-grained multicomputer algorithm for the longest common subsequence problem,” Parallel, Distributed and Network-Based Processing, 2003. Proc. Eleventh Euromicro Conference Feb. 2003, pp. 349-356.
[28] Y. Robert and M. Tchuente, “A systolic array for the longest common subsequence problem,” Inform. Proc. ICPP 1976, pp. 191-198.
[29] J. H. Chang, O. H. Ibarra and M. A. Palis, “Parallel parsing on one-way array of finite state machines,” IEEE Trans. Comput. 1987, pp. 64-75.
[30] Y. C. Lin, “New systolic arrays for the longest subsequence problem,” Paral. Comput. 20, 1994, pp. 1323-1334.
[31] G. Luce and J. F. Myoupo, “An Efficient Linear Systolic Algorithm for Recovering Longest Common Subsequences,” Algorithms and Architectures for Parallel Processing, 1995. ICAPP 95. IEEE First ICA/sup 3/PP. IEEE First International Conference on Volume 1, April 1995, pp. 20 – 29, vol. 1.
[32] R.A. Wagner and M. J. Fischer, “The String-to-String Correction Problem,” Journal of the ACM, vol. 21, no. 1, January 1975, pp. 168-173
[33] Claus Rick, “Simple and fast linear space computation of longest common subsequences,” 2000.pp. 275-281.

第一章緒論…………………………………………………….….………………......1
1.1 簡介…………………………………………….……..…….……………....
1.2 研究背景…………………………………..……….........…….………....2
1.3 研究目的………………………………..……….............…….……............
1.4 章節介紹…………………………………………...……….….…..…….4
第二章相關研究……………………………………………….………….………......5
2.1 基本概念與Lin心跳式陣列演算法與架構…........….…….……..…......6
第三章求解LCS方法之分析改進……………………………..…….………....……11
3.1 重疊等高線……………………………………....…..…………….…......11
3.2 分而擊破法……………………………………......…………….….......14
第四章 LCS處理器硬體架構......................………….…………....……...……............20
4.1 RS-232溝通模組………………………....……….....…………….……...21
4.2 心跳式陣列處理器模組……………....………….....…………….……...21
4.2.1 虛擬處理單元…………..………………...…………………….....22
4.3 控制器模組…………………...…....…….………..…....……….……...26
4.3.1 控制單元…………..………………………...........……………..26
4.3.1.1 Ctr init程序…………………………..…………...…....29
4.3.1.2 Physical PE operation程序…………..…………..........…29
4.3.1.3 Derive llcs程序…........................………………...…....29
4.3.1.4 Forward process程序…......................……………...……31
4.3.1.5 Backward process程序........…………....………......……31
4.3.1.6 Upload match location程序….……....…………...……...32
4.4 時間分析..........……………….................………...…………….….......33
第五章驗證與結果分析...............………….........………………………..…...............35
5.1 實作環境………………………......................……………..………….....35
5.2 時間評估……………………………………………......…..………….....36
第六章結論...............................................……………………………...………...........40
附錄A.......................................................………………………………...……...............41
參考文獻.................................................………………………………...……...............45