基于有限狀態(tài)自動機的多模式匹配算法研究.pdf

1、模式匹配是計算機應用領域重要的研究方向，廣泛應用于入侵檢測、信息檢索、生物科學計算等方面。隨著計算機網(wǎng)絡技術(shù)的飛速發(fā)展，數(shù)字信息量出現(xiàn)了爆炸式增長。如何提高模式匹配算法的性能成為人們研究的熱門課題。
　　 本文介紹了模式匹配技術(shù)的產(chǎn)生、發(fā)展和研究現(xiàn)狀，闡述了幾種重要的模式匹配算法，包括單模式匹配BF 算法、KMP 算法、BM 算法、BMH 算法、QS 算法和KR 算法等，多模式匹配AC 算法、AC_BM 算法、WM 算法等，研究

2、分析了它們的時間性能，并比較了各自的優(yōu)缺點。
　　 針對AC_BM 算法的不足之處，提出了一種改進的AC_QSS 算法。AC_QSS算法采用正向有限狀態(tài)自動機組織模式串，模式樹從右向左移動；每次移動模式樹前，檢查當前匹配窗口末字符及其后繼字符組成的字符串是否出現(xiàn)在模式樹中，可以有效提高模式樹的平均移動距離，減少不必要的字符比較次數(shù)，從而提高算法的時間效率。采用地址映射的方法查找字符串，在預處理階段將所有模式串的兩兩相鄰字符映射到