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

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

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