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

1、模式（字符串）匹配是計(jì)算機(jī)領(lǐng)域中的一個(gè)重要的研究方向，該問(wèn)題是計(jì)算機(jī)科學(xué)中的基礎(chǔ)問(wèn)題之一，在學(xué)術(shù)界和工業(yè)界有著廣泛的研究與應(yīng)用。模式匹配算法被廣泛應(yīng)用到涉及文本處理的各個(gè)領(lǐng)域，在網(wǎng)絡(luò)安全、信息檢索、文本過(guò)濾、以及生物信息學(xué)中都是關(guān)鍵問(wèn)題。隨著互聯(lián)網(wǎng)、海量文本檢索、計(jì)算生物信息學(xué)的高速發(fā)展，模式匹配問(wèn)題中的規(guī)則數(shù)也迅速的增大，模式匹配算法面臨的挑戰(zhàn)也越來(lái)越大。特別是在我國(guó)網(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)境下，對(duì)于中文字符集，本文提出了一種基于WM算法的改進(jìn)的多模式匹配算法----MSCZ算法。改進(jìn)策略包括：利用二級(jí)哈希策略削減了WM算法在中文較大規(guī)模模式集下的高內(nèi)存空間占用與高沖突的情況；對(duì)于中文模式串

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