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

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

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

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

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