技術領域

本發明涉及多模式匹配算法領域,是一種WM算法的改進算法。

背景技術

隨著網絡技術的發展，互聯網在人們日常生活中的作用越來越大，同時掛馬網頁、詐騙網頁、色情網頁等非法網站也給正常的網絡秩序帶來了巨大的挑戰，針對這種問題的一種處理方法是在網絡的關鍵位置，如內網與外網連接的邊界，布置基于網絡的入侵檢測系統(NIDS: Network-Based Intrusion Detection System),對非法網站的域名進行過濾。

發明內容

為了解決在最短模式長度較小的情況下，WM算法性能隨著模式集規模增大而顯著降低的問題，本發明在WM算法基礎上，進一步優化跳躍機制和匹配方法，并提出了模式分集的思想，設計了一種新的多模式匹配算法-SWM(SubsetWu-Manber)算法，并將其應用在域名過濾問題中，SWM算法的處理順序即字符串掃描從左向右，對模式的匹配從后向前進行。

1、預處理過程主要工作是建立多個檢索表，具體流程如下：

1)確定模式了集分界M，將模式集合分為P₁, P₂兩個子集；

2)統計得到P₁, P₂模式子集的最小模式長度m₁, m₂，確定匹配子串基本長度B；

3)對于P₁模式子集，按照最小模式長度m₁，構建SHIFT11, HASH1, PREFIX1三個表；

4)對于P₂模式子集，按照P₂子集的最小模式長度m₂，構建SHIFT21, SHIFT22, SHIFT23；HASH2,PREFIX2五個表

使用SHIFT23有兩個原因:一個原因是計算跳轉表索引的hash 1函數實現B個字符的hash計算，比PREFIX表的變長hash2函數運算簡單，相當于增加一次簡單的前綴確認;第二個原因是SHIFT23表是用于字符串B₃的匹配確認，而B₃遠離B₁、B₂，能夠一定程度上緩解連續相同字符串帶來的匹配沖突；

HASH1/HASH2每項包含模式鏈表指針、PREFIX1/PREFIX2表指針以及模式鏈表中最短模式長度，模式鏈表存儲經過多級匹配后hashl值相同的所有模式;PREFIXI/PREFIX2表存儲模式鏈表中每個模式按照最短模式長度計算的前綴hash(此處使用hash2函數)。

匹配從字符串的第m個字符開始，字符串的掃描從左向右;對模式的匹配是從右向左進行的，每次子串匹配的長度為B=2，設當前位置為i，則步驟如下:

1)計算B_i = t_i=B+1…t這B個字符的hashl值，得到h₁;

2)查SHIFT11表得到s_{1 1}=SHIFT 1 1(h₁ )，如果s _{1 1} = 0，轉7);如果s _{1 1}>0，計算B₄= t_i=B+1…t_i+1這B個字符的hashl值h₄，查SHIFT 11表得到s₁₄ = SHZFT11(h₄)，計算s₁=max(s_ips₁₄ +1);

3)查SHIFT21表得到s₂₁=SHIFT 21(h₁)，如果s₂₁>0，查表SHIFT21得到s₂₄=SHIFT 21(h₄)，計算s₂ = max(s₂₁, s₂₄ +1)，取s= min(s₁ , s₂ )，根據這個值向后移動相應的長度，并轉到1);如果s₂₁ = 0，則繼續;