簡易檢索 / 詳目顯示

回結果列表
研究生： 邱健鐘
論文名稱： 字串近似比對之硬體電路研究
指導教授： 黃文吉
學位類別： 碩士
Master
系所名稱： 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2007
畢業學年度： 95
語文別： 中文
論文頁數： 67
中文關鍵詞： 字串比對
論文種類： 學術論文
相關次數： 點閱：277  下載：1 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 字串比對在資訊科學上已被廣泛的應用，例如在資訊檢索、生物資訊上的DNA比對、文字搜尋、人工智慧等等，相關的演算法則也多如皮毛，如Knuth-Morris-Pratt algorithm [12]、Boyer-Morre algorithm [11] 等等，但諸如這些演算法則均偏重於軟體相關研究上，而當資料量變大時，所花的時間也就愈大，因此若能以硬體電路來處理，並利用硬體的優點來縮短比對所需的時間，同時也能達到平行化的功能，如此必能大幅提升效能。本論文針對以場域可程式閘陣列(FPGA)來實現近似字串比對的硬體電路， 並提出以Shift-And-Or法則為基礎的近似字串比對電路，此電路允許字串比對可以有插入(insert)、替代(substitution)及刪除(delete)三種錯誤，具有低邏輯單元(logic elements)數、擴充性佳、效能佳、可平行化處理等優點，最後並評估此電路在未來可應用的方向如音樂檢索等等的可行性。

    中文摘要 1 誌謝 ii 目錄 iii 附圖目錄 vi 附表目錄 x 第1章 序論................................................1 1.1 研究背景與動機........................................1 1.2 研究目標..............................................2 1.3 全文架構..............................................3 第2章 基本原理介紹 .........................................4 2.1 精確字串比對(Exact String Matching)...................4 2.1.1基本方式.............................................4 2.1.2軟體快速實現方式......................................6 2.2 近似字串比對(Approximate String Matching).............11 2.2.1基本方式............................................11 2.2.2 Edit Distance.....................................12 2.2.3動態規劃法..........................................13 第3章 近似比對的硬體實現(SHIFT-AND-OR架構)..................17 3.1 精確比對(Exact matching)..............................17 3.1.1 Shift-And法則......................................17 3.1.2實例................................................19 3.1.3 Shift-And電路......................................19 3.2 近似比對(Approximate Matching)........................20 3.2.1 Shift-And於Insert及實例.............................21 3.2.2 Shift-And於Insert電路...............................24 3.2.3 Shift-And於Delete及實例.............................25 3.2.4 Shift-And於Delete電路...............................28 3.2.5 Shift-And於Substitution及實例.......................29 3.2.6 Shift-And於Substitution電路.........................32 3.2.7 Shift-And於Insert、Delete、Substitution及實例........33 3.2.8 Shift-And於Insert、Delete、Substitution電路..........35 3.2.9 完整近似比對系統.....................................36 第4章 實驗數據與效能比較....................................39 第5章 結論及未來展望.......................................48 參考文獻..................................................50 附錄.....................................................54

    [1]Park, J. H., and George, K. M.,1999, “Parallel String Matching Algorithms Based on Dataflow,”Proceedings of the 32nd Hawaii International Conference on System Sciences.
    [2] Court, T. V., and Herbordt, M. C.,2006, “Families of FPGA-based accelerators for approximate string matching,” Microprocessors and Microsystems.
    [3] Wu, S. and Manber, U.,1992, “Fast Text Searching Allowing Errors,” Communications of the ACM, Vol. 35, No.10, pp.83-91.
    [4] Jacobi, R. P., Ayala-Rincon, M., Carvalho, L. G. A., and Hartenstein, R. W., 2005, “Reconfigurable systems for sequence alignment and for general dynamic programming,”Genetics and Molecular Research, pp. 543-552.
    [5] Sastry, R., Ranganathan, N., and Remedios, K., 1995, “CASM: A VLSI Chip for Approximate String Matching,”IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 17, No. 8, pp. 824-830.
    [6] Ranganathan, N., and Motamarri, R., 1997, “A VLSI Architecture for Computing the Optimal Correspondence of String Subsequences,” Computer Architectures for Machine Perception, pp. 290-294.
    [7] Mukherjee, A., 1989, “Hardware Algorithms for Determining Similarity Between Two String,” IEEE Transaction on Computers, Vol. 38, No. 4, pp. 600-603.
    [8] Navarro, G., 2001, “A Guided Tour to Approximate String Matching,” ACM Computer Surveys, Vol. 33, No. 1.
    [9] Bazea-Yates, R. A., and Gonnet, G. H., 1992, “A new approach to text searching,”Communication of the ACM, Vol. 35, No. 10, pp. 74-82.
    [10] Levenshtein, V. I., 1965, “Binary codes capable of correcting spurious insertions and deletions of ones.” Problems Inform. Transmission 1, pp. 8–17.
    [11] Boyer, R. and Moore, J., 1977, “A fast string searching algorithm.” Communication of the ACM, Vol. 20, No. 10, pp. 762-772.
    [12] Knuth, D. E., Morris, J. H., and Pratt, V. R., 1977, “Fast pattern matching in strings.” SIAM Journal on Computing, Vol. 6, pp. 323-350.
    [13] Ukkonen, E., 1985, “Finding Approximate Patterns in Strings.,” Journal of Algorithms, Vol. 6, pp. 132-137.
    [14] Ristad, E. S., and Yianilos, P. N., 1998, “Learning String-Edit Distance.” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 20, No. 5, pp. 522-532.
    [15] Shang, H., and Merrettal, T. M., 1996, “ Tries for approximate string matching,” Knowledge and Data engineering, IEEE Transactions on, Vol. 8, Issue: 4, pp. 540-547.
    [16] Nelson, M., 1996, “Fast String Searching With Suffix Trees,”Dr. Dobb’s Journal.
    [17] Kurtz, S., 1999, “Reducing the Space Requirement of
    Suffix Trees.” Software--Practice and Experience,
    29(13), pp. 1149-1171.
    [18] Weiner, P., 1973, “Linear pattern matching
    algorithms,”In Proceedings of IEEE Symposium on Switching
    and Automata Theory, pp. 1-11.
    [19] Lemstrom, K., 2000, “String Matching Techniques for Music Retrieval,” Department of Computer Sciencs Series of Publication A Report A.
    [20] 曾元顯, 2000, “ 音樂內容查詢不匹配問題與檢索模式之研究,”輔仁大學 圖書資訊學系 資訊傳播與圖書館學, Vol. 6, No. 4, pp. 35-48.

    QR CODE