[發(fā)明專利]一種海量規(guī)模的郵件地址匹配方法

在審

• 申請?zhí)枺?/td>: 201810508941.4
• 申請日: 2018-05-24
• 公開（公告）號: CN108764840A
• 公開（公告）日: 2018-11-06
• 發(fā)明（設(shè)計）人: 玄世昌;苘大鵬;王巍;楊武;趙恒
• 申請（專利權(quán)）人: 哈爾濱工程大學(xué)
• 主分類號: G06Q10/10
• 分類號: G06Q10/10;G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發(fā)明提供了一種海量規(guī)模的郵件地址匹配方法。選取海量規(guī)模下哈希耗時和哈希沖突處理優(yōu)秀的哈希模型，作為匹配方法的哈希函數(shù)。由于郵件地址的域名重復(fù)概率很大，利用布隆過濾器對郵件地址的進(jìn)行存儲以及匹配，以此降低匹配方法的內(nèi)存消耗和匹配效率。使用紅黑樹存儲哈希沖突后的模式串，提高算法全文匹配的性能。本發(fā)明針對WM匹配方法的存儲結(jié)構(gòu)和匹配流程進(jìn)行優(yōu)化。利用一種高效的哈希模型(BKDRHash)減少哈希沖突；通過布隆過濾器存儲和匹配郵件地址的域名，避免了郵件域名的重復(fù)存儲，降低了匹配方法的內(nèi)存消耗；通過使用紅黑樹處理產(chǎn)生哈希沖突的元素，降低全文匹配耗時。

技術(shù)領(lǐng)域

本發(fā)明涉及的是一種Wu-Manber多模式匹配方法。

背景技術(shù)

基于哈希過濾思想的Wu-Manber算法,簡稱WM算法。WM算法結(jié)合了BM算法的“壞字符”思想，是典型的基于后綴掃描的算法，只不過在實(shí)際應(yīng)用中WM算法利用的是字符塊。這意味著匹配失敗后，匹配指針可跳轉(zhuǎn)距離變大，提高了算法的匹配性能。WM算法在進(jìn)行匹配的時候,使用哈希表選擇模式串集合中的一個子集與當(dāng)前文本進(jìn)行全文匹配,減少無謂的匹配運(yùn)算。WM算法的最優(yōu)時間復(fù)雜度可以達(dá)到O(B n/m)(B是字符塊的長度,m是最短模式長度)。WM算法的執(zhí)行時間不會隨著模式集的增加而成比例增長，且算法運(yùn)行所需的內(nèi)存占用量小。

基于郵件地址匹配的郵件過濾技術(shù)是實(shí)現(xiàn)郵件安全網(wǎng)關(guān)的一種關(guān)鍵技術(shù)。基于WM匹配方法實(shí)現(xiàn)郵件地址匹配主要有三個關(guān)鍵點(diǎn)：

1)針對郵件地址特征進(jìn)行方法優(yōu)化，方法的內(nèi)存消耗有待優(yōu)化；

2)海量規(guī)模匹配場景下，哈希沖突嚴(yán)重。WM算法是基于哈希思想的算法，采用字符塊哈希，這種情況下將WM算法應(yīng)用于模式串集合規(guī)模不大的情況下，哈希沖突對算法性能產(chǎn)生的影響不大。當(dāng)應(yīng)用于海量模式串集合時哈希沖突將會非常嚴(yán)重，需要采用優(yōu)秀的字符哈希算法；

3)海量規(guī)模匹配場景下全文匹配耗時嚴(yán)重。傳統(tǒng)的WM算法在匹配的過程中，當(dāng)查詢跳轉(zhuǎn)表(SHIFT)的跳轉(zhuǎn)距離為0的時候，需要對模式串和目標(biāo)文本進(jìn)行全文匹配。產(chǎn)生哈希沖突的模式串存儲在鏈表中，這是傳統(tǒng)的處理方式，在全文精確匹配的時候就要逐一遍歷鏈表，檢查是否匹配成功，雖然采取了PREFIX表可以減少精確匹配的次數(shù)，提高匹配效率，但是這種順序查找的方式，對于海量模式串集合來說，PREFIX表的性能提升效果并不明顯。

發(fā)明內(nèi)容

本發(fā)明的目的在于提供一種在海量規(guī)模郵件地址匹配場景下能夠表現(xiàn)出良好時間和空間性能的海量規(guī)模的郵件地址匹配方法。

本發(fā)明的目的是這樣實(shí)現(xiàn)的：

1、預(yù)處理階段：

1.1、先存儲郵件地址的用戶名部分；

1.2、將域名部分通過布隆過濾器進(jìn)行存儲；

1.3、根據(jù)用戶名部分生成SHIFT表和HASH表；

1.4、利用紅黑樹處理產(chǎn)生哈希沖突的用戶名，根據(jù)用戶名的前綴字符串計算出鍵值，再將每個用戶名插入到根據(jù)用戶名后綴塊哈希索引到的紅黑樹中；

2、掃描階段：

2.1、根據(jù)當(dāng)前文本匹配窗口的后綴字符塊的哈希值找到其SHIFT值，如果SHIFT值不為0，則匹配窗口向后跳轉(zhuǎn)SHIFT值，繼續(xù)匹配；若SHIFT值為0,利用當(dāng)前窗口的后綴字符塊計算出哈希值，轉(zhuǎn)到步驟2.2；

2.2、通過HASH表索引到相應(yīng)的紅黑樹，如果索引到的紅黑樹不為空，通過當(dāng)前窗口的前綴字符串索引，在該紅黑樹中進(jìn)行精確匹配，若在紅黑書樹中匹配成功，則轉(zhuǎn)入步驟2.3，否則失敗；若索引到的紅黑樹為空，匹配失敗；在此步驟匹配失敗，匹配窗口向后跳轉(zhuǎn)，轉(zhuǎn)到步驟2.1；