中英混合多模式匹配算法的改進(jìn)及GPU并行化研究.pdf

1、隨著計(jì)算機(jī)、通信與網(wǎng)絡(luò)的飛速發(fā)展，信息泄漏等問(wèn)題受到了越來(lái)越多的關(guān)注。基于內(nèi)容的網(wǎng)絡(luò)信息審計(jì)，是保證信息不被泄漏，防止非法信息傳播的有效手段，其關(guān)鍵技術(shù)為多模式文本匹配。在我國(guó)現(xiàn)有的網(wǎng)絡(luò)環(huán)境下，多模式文本匹配將會(huì)面臨中英文混合處理這一特殊難題。傳統(tǒng)的多模式匹配在此環(huán)境下，則會(huì)產(chǎn)生空間膨脹、誤匹配或漏匹配等問(wèn)題。且隨著網(wǎng)絡(luò)數(shù)據(jù)信息規(guī)模的日益增加，對(duì)內(nèi)容審計(jì)的實(shí)時(shí)性有了更高的要求。論文的主要工作包括:
　　 (1)在Trie結(jié)構(gòu)的基

2、礎(chǔ)上，提出了一種基于節(jié)點(diǎn)添加的中英混合多模式匹配算法—NA-Trie。該算法通過(guò)添加少量的節(jié)點(diǎn)，以避免中文首字節(jié)錯(cuò)位匹配等問(wèn)題。算法能夠正確處理模式串同時(shí)含有中英文字符這一情況，有效避免錯(cuò)誤匹配的發(fā)生;并且簡(jiǎn)化匹配過(guò)程，消去了多余的分支語(yǔ)句，使得算法更易于并行加速。給出一種基于記憶化存儲(chǔ)狀態(tài)結(jié)果的優(yōu)化算法，通過(guò)預(yù)處理所有狀態(tài)節(jié)點(diǎn)，記憶化地保存各狀態(tài)所能獲得的匹配數(shù)。該算法降低了匹配算法的時(shí)間常數(shù)，減少了時(shí)間開(kāi)銷(xiāo)，在一定程度上提高了匹配效

3、率。
　　 (2)分多個(gè)小文本、單個(gè)大文本兩種情況，利用GPU對(duì)多模式匹配進(jìn)行并行優(yōu)化。并針對(duì)單個(gè)大文本情形，給出一種基于文本拆分的并行文本匹配算法。該算法通過(guò)預(yù)處理以去除中文文本的數(shù)據(jù)相關(guān)性，再進(jìn)行文本拆分和并行匹配，以大幅提升算法匹配效率。設(shè)計(jì)并實(shí)現(xiàn)了一種基于GPU的通用并行文本匹配原型系統(tǒng)，該原型系統(tǒng)模塊化了并行匹配過(guò)程，提供了統(tǒng)一的函數(shù)接口。研究人員只需將自己的核心匹配代碼嵌入到接口函數(shù)中，即可完成多模式匹配算法的并行優(yōu)