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

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

2、研究內(nèi)容包括： 對雙向有限狀態(tài)自動機(2DFA)進行擴展，提出了讀頭可跳躍的確定的有限狀態(tài)自動機(SDFA)。證明了SDFA的描述能力與DFA是等價的。其次，分析了串匹配算法讀頭運動的四種類型并將它們用SDFA來模型化，并給出了一個典型例子：讀頭移動最復雜的BMA串匹配算法的SDFA模型，來證明SDFA模型的簡練性與準確性?！　√岢隽耸褂孟嗷ブ丿B的大窗口來掃描正文的思想的LDM單模式串匹配算法。在窗口中，先從中間位置往前掃描模

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