使用位元平行運算改良精確字串比對演算法

Using Bit-Parallel Operations to Improve Exact String Matching Algorithms

洪晢為(Che-Wei Hung)

指導教授 ： 黃光璿

國立暨南國際大學/科技學院/資訊工程學系/碩士(2021年)

https://doi.org/10.6837/ncnu202100273

摘要

字串比對問題是電腦科學領域的重要問題，本篇論文所討論的範圍屬於其中的單精確字串比對問題，我們會先解釋不同的字串比對演算法，接著會講述使用位元平行運算技巧的字串比對演算法，例如Shift-And演算法、BNDM演算法，最後我們探討如何於位元平行運算演算法融入字串比對演算法，用來改善BNDM演算法的表現。

關鍵字

精確字串比對 ； 字串比對 ； 位元平行運算

並列摘要

The string matching problem is an important issue in the field of computer science. The scope of this paper belongs to the exact single string comparison problem. We will first explain different string-matching algorithms, and then we will talk about the use of bit- parallel techniques for string matching, such as Shift-And algorithm and BNDM algorithm. Finally, we will discuss how to integrate the bit-parallel computing algorithm into the string-matching algorithm to improve the performance of the BNDM algorithm.

並列關鍵字

exact string matching ； string matching ； bit-parallel operation

參考文獻

[1] Morris Jr, J., & Pratt, V. (1970). A linear pattern-matching algorithm. Report 40. University of California, Berkeley.

[2] Knuth, D. E., Morris, J., James H, & Pratt, V. R. (1977). Fast pattern matching in strings. SIAM journal on computing, 6(2), 323-350.

[3]Boyer, R. S., & Moore, J. S. (1977). A fast string searching algorithm. Communications of the ACM, 20(10), 762-772.

[4] Sunday, D. M. (1990). A very fast substring search algorithm. Communications of the ACM, 33(8), 132-142.

[5] Dömölki, B. (1964). An algorithm for syntactical analysis. Computational Linguistics, 3(29-46), 151.