面向網(wǎng)絡內(nèi)容篩選的串匹配技術(shù)研究.pdf

1、串匹配是計算機科學理論中的一個經(jīng)典問題，它指在一個符號串中尋找具有特定性質(zhì)的模式，比如在一個字符串中尋找某個子串。對于這個古老的問題，已經(jīng)有很多的研究，也有很多優(yōu)秀的算法。 然而近年來，隨著網(wǎng)絡和生物信息學的發(fā)展，對于串匹配技術(shù)提出了許多新的需求，對于這個經(jīng)典問題大家又重新產(chǎn)生了濃厚的興趣。在網(wǎng)絡技術(shù)中，隨著網(wǎng)絡應用的日漸普及，網(wǎng)絡信息在迅速膨脹，因此如何能夠及時、準確、安全地在龐大的實時網(wǎng)絡信息流中獲得特定的信息，已經(jīng)成為網(wǎng)絡

2、信息安全領(lǐng)域的熱點問題。由于數(shù)據(jù)量的龐大、檢索的實時性以及待檢索文本的結(jié)構(gòu)化等需求，因此必須有針對性地改進已有的串匹配技術(shù)，才能夠解決網(wǎng)絡信息過濾問題。 本文即為解決此問題的一項嘗試，并取得了如下成果： 1.分析總結(jié)了部分經(jīng)典算法在隨機數(shù)據(jù)上的性能：本文總結(jié)了當前精確模式串匹配算法的研究現(xiàn)狀，包括針對單模式串的KMP算法、Boyer Moore算法和BOM(BackwardOracle Matching)算法，針對多模式

3、串的Aho Corasick算法、Wu Manber算法和SBOM．(Set Backward Oracle Matching)算法。從理論的角度，本文對這些算法的平均時間復雜度進行了初步分析；并在隨機的網(wǎng)絡數(shù)據(jù)測試集合上，驗證了以上結(jié)論；進而總結(jié)出多模式串匹配算法性能的4條性質(zhì)。 2.提出了多模式串匹配的劃分策略：經(jīng)典的多模式匹配算法，在模式數(shù)目多于5000時性能有著明顯的下降。針對這個問題，本文提出了分組的策略以提高匹配性能

4、。本文證明了最優(yōu)劃分的兩個性質(zhì)：一是最優(yōu)劃分的連續(xù)性定理，一是最優(yōu)劃分的等長分組性定理。 3.設計并實現(xiàn)了一種大規(guī)模多模式串匹配的算法一COM：它使用動態(tài)規(guī)劃方法或最短路徑方法求解最優(yōu)的劃分，并對每組進行訓練以得到一種最適用的串匹配方法。實驗結(jié)果表明，COM算法的掃描匹配速度是傳統(tǒng)算法的l一3倍。 4.提出了針對結(jié)構(gòu)化的XML文本的快速串匹配的算法一XMatch：在對于XML，文本的含路徑信息的模式串匹配中，由于XML文