面向網絡內容篩選的串匹配技術研究.pdf

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

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

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

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