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

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

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

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