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

有效

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

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，按照此方法一直找到哈希值對應的分隔符；

c）判斷哈希值hi(x)，i=（1,2,3…k）對應的計數位是否全部大于0，若否則認為該元素不在FPVLCBF中，若是則跳轉到步驟d；

d）判斷哈希值hi(x)，i=（1,2,3…k）對應的計數位是否全部大于1，若是則認為查詢成功，若否則轉e；

e）判斷計數值為1的元素的指紋位值與指紋函數的函數值hp(x)是否相同，若全部相同則元素在此集合中，否則元素不在此集合中；

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）跳過指紋位，將指紋位后面第二比特之后的所有比特位左移一位，覆蓋指紋位之后的第一個比特位；

e）更新索引表。