以Boyer-Moore 演算法為基礎改良之近似字串比對演算法

An Improved Approximate String Matching Algorithm Based upon the Boyer-Moore Algorithm

謝一功(Yi-Kung Shieh)

指導教授 ： 李家同

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

https://doi.org/10.6837/NCNU.2008.00266

摘要

在這篇論文中，我們探討精確字串比對問題以及近似字串比對問題，我們避免使用暴力法將問題解出。我們將Boyer-Moore 演算法中的壞字元法則改良，並與Horspool 演算法做比較，最後，我們發現改良過後的演算法可以本身包含了Horspool 演算法的資訊，因此我們可以將此兩種方法結合，使用這種結合方法可以讓我們將比較時的視窗移動更遠。

關鍵字

精確字串比對 ； 近似字串比對 ； 壞字元法則

並列摘要

In this thesis, we discuss the exact string matching problem and approximate string matching problem. We avoid using a brute-force algorithm to solve the string matching problem. We improve the Bad Character Rule of Boyer and Moore Algorithm and compare it with the Horspool Algorithm. And we find that the improved method include the information of the Horspool Algorithm. Therefore, we combine the improved method with the Horspool Algorithm. The combinative method has a better efficiency in searching phase.

並列關鍵字

Exact string matching ； Approximate string matching ； Bad Character Rule

參考文獻

[BM77] A fast string searching algorithm, BOYER, R.S., MOORE, J.S, Communications of the ACM., Vol. 20, 1977, p.p. 762-772.

[CL2007] String Matching Algorithms Based upon the Uniqueness Property, C. W. Lu and R. C. T. Lee, The 24th Workshop on Combinatorial Mathematics and Computation Theory, pp.385-392, 2007.

[H80]. Practical Fast Searching in Strings, Horspool, R.N., Software - Practice and Experience,vol. 10, pp. 501-506, 1980.

[HS91] Fast string searching , HUME A. and Sunday D.M., Software - Practice & Experience 21(11), pp. 1221-1248, 1991.

[R92] Tuning the Boyer-Moore-Horspool string searching algorithm, T. RAITA, Software - Practice & Experience, 22(10):879-884, 1992.