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

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

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

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