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

1、模式匹配是計算機(jī)應(yīng)用領(lǐng)域重要的研究方向之一,廣泛應(yīng)用于入侵檢測、信息檢索、生物科學(xué)等方面。隨著計算機(jī)網(wǎng)絡(luò)技術(shù)的飛速發(fā)展,信息量呈爆炸式增長,如何提高模式匹配算法的性能成為了信息檢索、內(nèi)容過濾等領(lǐng)域研究的熱門課題。
　　本文介紹了幾種重要的模式匹配算法,包括單模式匹配和多模式匹配算法,如BF算法、BM算法、QS算法和AC算法、AC_BM算法、WM算法等,分析了它們的時間性能,并比較了各自的優(yōu)缺點。
　　隨著中文模式串?dāng)?shù)目的增加

2、,基于有限狀態(tài)自動機(jī)的多模式匹配算法的存儲空間會快速膨脹,goto函數(shù)以及查詢跳轉(zhuǎn)距離的計算量大,從而導(dǎo)致算法的時空性能急劇下降。針對該問題,本文提出了帶跳轉(zhuǎn)距離的鄰接鏈表存儲方式,為每一狀態(tài)建立一個單鏈表,所有單鏈表與頂點表構(gòu)成鄰接鏈表,并與跳轉(zhuǎn)距離表融為一體,可同時完成狀態(tài)與跳轉(zhuǎn)距離的查詢,提高了算法的時空效率?；趲D(zhuǎn)距離的鄰接鏈表存儲方式,設(shè)計了一種適合中文的多模式匹配算法—AC_SC算法,并分析了AC_SC算法的時空性能。<