最優(yōu)串匹配算法及其在網(wǎng)絡(luò)安全中的應(yīng)用.pdf

1、　　串匹配算法是計(jì)算機(jī)科學(xué)領(lǐng)域中一個(gè)重要的基礎(chǔ)研究領(lǐng)域。在文本處理、數(shù)據(jù)壓縮、搜索引擎、生物計(jì)算，以及網(wǎng)絡(luò)安全等大量的應(yīng)用中，都需要進(jìn)行串匹配。本文主要討論精確模式串匹配。本文首先研究了模式串匹配的模型化方法，提出了使用一個(gè)寬窗口來(lái)在正文中并行地掃描多個(gè)模式出現(xiàn)的思想，并將它應(yīng)用到單模式匹配和多模式匹配中來(lái)，然后將它們與Bit-Parallelism技術(shù)結(jié)合，獲得了幾個(gè)時(shí)間最優(yōu)的串匹配算法。最后給出了這些算法在網(wǎng)絡(luò)安全中的一些應(yīng)用。主要

2、研究?jī)?nèi)容包括： 對(duì)雙向有限狀態(tài)自動(dòng)機(jī)(2DFA)進(jìn)行擴(kuò)展，提出了讀頭可跳躍的確定的有限狀態(tài)自動(dòng)機(jī)(SDFA)。證明了SDFA的描述能力與DFA是等價(jià)的。其次，分析了串匹配算法讀頭運(yùn)動(dòng)的四種類型并將它們用SDFA來(lái)模型化，并給出了一個(gè)典型例子：讀頭移動(dòng)最復(fù)雜的BMA串匹配算法的SDFA模型，來(lái)證明SDFA模型的簡(jiǎn)練性與準(zhǔn)確性。　　提出了使用相互重疊的大窗口來(lái)掃描正文的思想的LDM單模式串匹配算法。在窗口中，先從中間位置往前掃描模

3、式前綴，然后再掃描相應(yīng)的模式后綴。將Bit-Parallelism技術(shù)與LDM算法思想結(jié)合，提出了在模式串長(zhǎng)度不大于機(jī)器字長(zhǎng)的情況下各項(xiàng)時(shí)間復(fù)雜度與LDM算法相同的算法LNDM。性能測(cè)試實(shí)驗(yàn)也驗(yàn)證了它們平均時(shí)間復(fù)雜度最優(yōu)這一理論結(jié)果，而且在查找較短模式時(shí)，LNDM算法與LDM算法在大字母表情況下是最快的。　　將LDM算法的思想推廣到多模式匹配中來(lái)，提出了MLDM算法。　　提出了一個(gè)使用動(dòng)態(tài)連接庫(kù)來(lái)實(shí)現(xiàn)的PLUGIN技術(shù)的可擴(kuò)展的網(wǎng)絡(luò)