[發(fā)明專利]一種用于URL過濾系統(tǒng)的URL查找方法

無效

• 申請?zhí)枺?/td>: 200910087509.3
• 申請日: 2009-06-23
• 公開（公告）號: CN101605129A
• 公開（公告）日: 2009-12-16
• 發(fā)明（設計）人: 嵩天;周舟;賈云得
• 申請（專利權(quán)）人: 北京理工大學
• 主分類號: H04L29/06
• 分類號: H04L29/06;H04L9/36
• 代理公司: 北京理工大學專利中心
• 代理人: 張利萍

1.一種用于URL過濾系統(tǒng)的URL查找方法，其特征在于：該方 法將已有URL查找方法中的哈希方法與多字符串匹配的方法相結(jié) 合，其具體步驟如下：

步驟一、壓縮URL黑名單

首先，將URL黑名單進行壓縮，具體操作步驟如下：

第(1)步：基于URL語法格式，根據(jù)分隔符“://”和“/”，將 原始的URL分解成scheme子項、host子項以及path子項，其中path 子項為空或多項；

第(2)步：將第(1)步分解出的每個變長的host子項以及path 子項，利用c位的哈希函數(shù)壓縮成c/8個字節(jié)的字符串；此處忽略 scheme子項，即不對scheme子項進行計算；

第(3)步：將壓縮后的各個子項按原有次序連接成一個字符串 并存儲，用其代替原始的URL；

對黑名單中的每一個URL都采用上述(1)～(3)步進行處理， 得到壓縮后的黑名單；

步驟二、為壓縮后的URL黑名單建立一個后綴表和一個前綴表

在步驟一的基礎上，為壓縮后的URL黑名單建立一個后綴表和 一個前綴表，具體操作步驟如下：

首先計算壓縮后的黑名單中URL的最短長度，記為m；然后對 所有壓縮后的URL的前m個字符建立一個后綴表，記為SUFFIX， 以及一個前綴表，記為PREFIX；后綴表和前綴表的建立方法采用 Wu-Manber方法中的哈希表以及前綴表的建立方法；后綴表的每個表 項指向最后B個字符被哈希到該表項的URL，如果有多個URL被哈 希到同一表項，則采用鏈式存儲結(jié)構(gòu)；前綴表存儲的是每個模式前B’ 個字符的哈希值；B和B’為正整數(shù)，其值根據(jù)實驗情況擇優(yōu)選擇；建 立后綴表和前綴表所用到的哈希函數(shù)可根據(jù)不同情況進行選擇；

步驟三、查找請求URL

在步驟二的基礎上，判斷一個請求的URL是否在黑名單中，具 體操作步驟如下：

第(1)步：使用步驟一中的壓縮步驟將請求URL壓縮成(c/8)*n 個字節(jié)的字符串，n是分解出的URL子項的數(shù)目；

第(2)步：判斷(c/8)*n的值是否小于m，如果小于則報告“未 發(fā)現(xiàn)”，并結(jié)束過程；否則轉(zhuǎn)到第(3)步；

第(3)步：使用步驟二建立后綴表所用到的哈希函數(shù)，計算壓 縮后的請求URL中B個字符，即從第m-B+1個字符到第m個字符 的哈希值h；

第(4)步：使用步驟二建立前綴表所用到的哈希函數(shù)，計算壓 縮后的請求URL前B’個字符的哈希值，記為“URL前綴”；

第(5)步：判斷SUFFIX[h]指針指向的URL是否為空，如果為 空，則報告“非發(fā)現(xiàn)”，并結(jié)束過程；否則，轉(zhuǎn)到第(6)步；

第(6)步：檢查SUFFIX[h]指針指向的URL在PREFIX表中的 值是否等于“URL前綴”；如果不相等，轉(zhuǎn)到第(7)步；如果相等， 則將該URL與壓縮后的請求URL進行逐個字符的比較，如果壓縮后 的請求URL的前綴與SUFFIX[h]指針指向的URL完全匹配，則報告 “發(fā)現(xiàn)”，并結(jié)束過程；否則，轉(zhuǎn)到第(7)步；

第(7)步：移動SUFFIX[h]指針，指向下一個URL，判斷是否 為空，如果為空，則報告“未發(fā)現(xiàn)”，并結(jié)束過程；否則，轉(zhuǎn)到第(6) 步。