基于漢字編碼特征的中文多模式匹配算法研究.pdf

1、近年來(lái)網(wǎng)絡(luò)的高速發(fā)展，信息呈爆炸式增長(zhǎng)，模式匹配是內(nèi)容過(guò)濾和信息檢索的核心技術(shù)，成為計(jì)算機(jī)應(yīng)用和信息安全領(lǐng)域中的重要研究方向。對(duì)大規(guī)模中文模式匹配，已有模式匹配算法的時(shí)間和空間性能都難以滿(mǎn)足需求。因此，提高中文模式匹配算法的時(shí)間效率，對(duì)于提高計(jì)算機(jī)應(yīng)用系統(tǒng)的性能有重要意義。
　　本文介紹了幾種經(jīng)典模式匹配算法，包括BF算法、BM算法以及Sunday算法等，深入研究了AC、AC_BM以及WM等多模式匹配算法，詳細(xì)描述了各算法的匹配過(guò)

2、程，分析了它們的優(yōu)缺點(diǎn)以及時(shí)間性能。
　　AC及其改進(jìn)算法基于有限狀態(tài)自動(dòng)機(jī)，對(duì)于大規(guī)模中文模式串匹配，由于漢字的散度較高，導(dǎo)致有限狀態(tài)自動(dòng)機(jī)中的零狀態(tài)過(guò)長(zhǎng)，在查找零狀態(tài)字符時(shí)耗時(shí)較多，算法的效率急劇下降。針對(duì)此問(wèn)題，本文提出了一種基于漢字編碼特征混合存儲(chǔ)結(jié)構(gòu)，并提出了相應(yīng)的中文多模式匹配算法，該算法有如下特點(diǎn):
　　(1)考慮到漢字編碼的首字節(jié)范圍比尾字節(jié)范圍小，因此，先查找首字節(jié)，再查找尾字節(jié)，由于首字節(jié)查找失敗后直接跳

3、轉(zhuǎn)，一定程度上避免了查找尾字節(jié)，降低了查找時(shí)間。
　　(2)對(duì)狀態(tài)字符設(shè)置匹配標(biāo)記，當(dāng)字符的匹配標(biāo)記為0時(shí)，不再匹配模式串后繼字符，有效避免重復(fù)匹配以及部分匹配，節(jié)省了匹配時(shí)間。
　　(3)將跳轉(zhuǎn)距離存儲(chǔ)在狀態(tài)鏈表和匹配桶中，在確定下一跳轉(zhuǎn)距離時(shí)同時(shí)查找跳轉(zhuǎn)距離，避免了重復(fù)查找跳轉(zhuǎn)距離，提高了算法的匹配效率。
　　最后，對(duì)有限狀態(tài)自動(dòng)機(jī)的不同存儲(chǔ)方式和不同跳躍式匹配算法的時(shí)間性能進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果表明，本文混合存儲(chǔ)結(jié)構(gòu)