中文多模式匹配算法及其并行化研究與實現(xiàn).pdf

1、模式（字符串）匹配是計算機領(lǐng)域中的一個重要的研究方向，該問題是計算機科學(xué)中的基礎(chǔ)問題之一，在學(xué)術(shù)界和工業(yè)界有著廣泛的研究與應(yīng)用。模式匹配算法被廣泛應(yīng)用到涉及文本處理的各個領(lǐng)域，在網(wǎng)絡(luò)安全、信息檢索、文本過濾、以及生物信息學(xué)中都是關(guān)鍵問題。隨著互聯(lián)網(wǎng)、海量文本檢索、計算生物信息學(xué)的高速發(fā)展，模式匹配問題中的規(guī)則數(shù)也迅速的增大，模式匹配算法面臨的挑戰(zhàn)也越來越大。特別是在我國網(wǎng)絡(luò)安全領(lǐng)域中，當(dāng)前一些模式匹配算法已經(jīng)很難滿足在中文字符環(huán)境下的較

2、大規(guī)模模式集匹配系統(tǒng)的性能要求。因此，迫切需要在較大規(guī)模模式串下構(gòu)造性能突出的模式匹配算法。
　　本文首先介紹了模式匹配的一些經(jīng)典算法，如BF算法、KMP算法、BM算法、AC算法、AC_BM算法和WM算法。其次，在較大規(guī)模多模式環(huán)境下，對于中文字符集，本文提出了一種基于WM算法的改進(jìn)的多模式匹配算法----MSCZ算法。改進(jìn)策略包括：利用二級哈希策略削減了WM算法在中文較大規(guī)模模式集下的高內(nèi)存空間占用與高沖突的情況；對于中文模式串

3、出現(xiàn)的前綴包含情況，通過模式串前綴壓縮策略，解決了HASH表中模式串鏈過長的問題；通過進(jìn)一步對壓縮后的HASH表模式串鏈，建立二叉查找樹，將原有 WM算法查找時的線性時間復(fù)雜度轉(zhuǎn)化為了對數(shù)時間復(fù)雜度，提升了算法在模式集規(guī)模較大時性能。實驗表明 MSCZ算法相對于WM算法在性能上有了較大的提升。最后，對MSCZ算法在Hadoop Mapreduce框架下進(jìn)行了并行化設(shè)計與實現(xiàn)。提出了MSCZ算法的Hadoop Mapreduce并行化方案