[發明專利]一種基于指紋型可變長布魯姆過濾器的郵件地址匹配方法

有效

• 申請號: 201710158175.9
• 申請日: 2017-03-16
• 公開（公告）號: CN108632131B
• 公開（公告）日: 2020-10-20
• 發明（設計）人: 王志剛
• 申請（專利權）人: 哈爾濱英賽克信息技術有限公司
• 主分類號: H04L12/58
• 分類號: H04L12/58;G06F16/22;G06F16/245
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明提供了一種基于指紋型可變長布魯姆過濾器的郵件地址匹配方法，FPVLCBF使用一個長度為m的向量V來表示一個集合，向量V中的每一維度i由三部分構成，第一部分是分隔符占1bit，第二部分是由a bit組成的計數器，第三部分是由b bit組成的指紋位；一共需要k+1個哈希函數，前k個函數的使用方法和傳統的布魯姆過濾器一樣用來計算哈希值，最后一個哈希函數用來計算一個元素的指紋值，FPVLCBF需要一個索引表來加快查找速度；將指紋的思想與計數布魯姆過濾器的思想相結合，提出了一種基于指紋的可變長計數布魯姆過濾器（FPVLCBF），降低了傳統計數布魯姆過濾器的假陽率，并最大程度上提高計數布魯姆過濾器的空間效率。

技術領域

本發明涉及郵件地址過濾技術領域，尤其涉及一種基于指紋型可變長布魯姆過濾器的郵件地址匹配方法。

背景技術

郵件地址匹配技術作為郵件網關技術中的基礎發揮著重要的作用。在當今互聯網日益復雜的今天，隨著網絡流量的逐漸增大，如何使得郵件網關在應對大流量網絡時，能夠擁有更高的處理速度，以及較好的內存消耗表現是當前郵件網關領域的主要需求。

目前絕大多數進行郵件地址匹配的方法選用的都是各類多模式匹配算法。以經典AC算法為例，采用AC算法進行郵件地址匹配可以獲得較好的時耗上的效率。但是AC算法在模式規則集數量較大時，需要的內存比較大。在郵件地址匹配方面，郵件地址的長度基本固定在一個范圍內，郵件地址過濾是在一個郵件地址集合中查找某個郵件地址是否在集合中。計數布魯姆過濾器在此類場合中的應用比較廣泛，但是計數布魯姆過濾器的空間復雜度較高，而且假陽率也比較高。

發明內容

本發明對傳統的計數布魯姆過濾器算法進行了改進，將指紋的思想與計數布魯姆過濾器的思想相結合，提出了一種基于指紋的可變長計數布魯姆過濾器（FPVLCBF），降低了傳統計數布魯姆過濾器的假陽率，并最大程度上提高計數布魯姆過濾器的空間效率。本發明非常適合用在大流量環境下的郵件地址匹配中。

為解決上述技術問題，本發明提供了1、一種基于指紋型可變長布魯姆過濾器的郵件地址匹配方法，其特征在于，FPVLCBF使用一個長度為m的向量V來表示一個集合，向量V中的每一維度i由三部分構成，第一部分是分隔符占1bit，第二部分是由a bit組成的計數器，第三部分是由b bit組成的指紋位；一共需要k+1個哈希函數，前k個函數的使用方法和傳統的布魯姆過濾器一樣用來計算哈希值，最后一個哈希函數用來計算一個元素的指紋值，FPVLCBF需要一個索引表來加快查找速度；

其中，FPVLCBF的插入步驟如下：

a）根據插入對象x，計算x的散列值hi(x)，i=（1,2,3…k），并計算指紋函數值hp(x)；

b）查找哈希值hi(x)，i=（1,2,3…k）對應的分隔符，查找時，通過計算先在索引表中找到最后一個小于hi(x)的值，從索引表中記錄的對應位的分隔符0開始，遇到0跳過b位，然后跳過若干位比特值為1的位，找到下一個0，分隔符計數值加1，按照此方法一直找到哈希值對應的分隔符；

c）跳過分隔符位，將指紋位值與特征函數的值hp(x)相異或，并將結果寫回到指紋位；

d）跳過指紋位，將指紋位之后的所有比特位右移一位，增加一個bit位，并將該bit置1；

e）更新索引表；

FPVLCBF的查詢步驟如下：

a）根據查詢元素x，算出x的哈希函數值hi(x)，i=（1,2,3…k），并計算指紋函數值hp(x)；

b）查找哈希值hi(x)，i=（1,2,3…k）對應的分隔符，查找時通過計算找到索引表中的最后一個小于hi(x)的值，從索引表中記錄的對應位的分隔符0開始，遇到0跳過b位，然后跳過若干位比特值為1的位，找到下一個0，分隔符計數值加1，按照此方法一直找到哈希值對應的分隔符；