字串近似比對之硬體電路研究

Abstract

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