[發(fā)明專利]一種基于海明距離的近似成員查詢方法

在審

• 申請?zhí)枺?/td>: 201810647790.0
• 申請日: 2018-06-22
• 公開（公告）號: CN109034197A
• 公開（公告）日: 2018-12-18
• 發(fā)明（設(shè)計）人: 錢江波;黃志鵬;陳葉芳;陳華輝
• 申請（專利權(quán)）人: 寧波大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 寧波奧圣專利代理事務所(普通合伙) 33226
• 代理人: 程曉明

1.一種基于海明距離的近似成員查詢方法，其特征在于構(gòu)建具有m個比特向量的布隆過濾器，記為HLBF，并將每個比特位的初始值置0；隨機產(chǎn)生L組，每組k個的隨機整數(shù)，設(shè)為h_i，j，其中i＝1，2，…，k，j＝1，2，…，L，h_i，j∈[1，w]，均勻分布，w是二進制數(shù)據(jù)長度；

由上述h_i，j對集合Ω中二進制數(shù)據(jù)采樣為比特組，構(gòu)成HLBF的第一層哈希；通過對每個比特組隨機哈希，得到b個地址，將HLBF這些地址上的比特置為1，得到HLBF的第二層哈希；對于給定的查詢數(shù)據(jù)Q，通過隨機翻轉(zhuǎn)Q上s個比特生成c個虛擬數(shù)據(jù)，對于每一個虛擬數(shù)據(jù)生成L個位串，若一個位串在布隆過濾器HLBF中的b個地址的比特位都為1，則稱該位串通過，若c個虛擬數(shù)據(jù)，每個虛擬數(shù)據(jù)有L個位串，即c*L個位串中任意一個通過，則判定查詢數(shù)據(jù)Q是集合Ω的近似成員。

2.如權(quán)利要求1所述的一種基于海明距離的近似成員查詢方法，其特征在于具體方法為：

構(gòu)建一個容量為m的位向量HLBF，地址為1到m，其中m是比特向量的個數(shù)；

設(shè)定每個比特向量的初始值HLBF[t]＝0，t＝1，2，…，m；

隨機產(chǎn)生L組，每組k個的隨機整數(shù)，設(shè)為h_i，j，其中i＝1，2，…，k，j＝1，2，…，L，h_i，j∈[1，w]，均勻分布，w是二進制數(shù)據(jù)長度；

對集合Ω中的每一個長度為w的二進制數(shù)據(jù)O_y，y＝1，2，…，n，生成L個位串，即bitgroup_y，j＝j(luò)$O_y[h_1，j]$O_y[h_2，j]$…$O_y[h_k，j]，其中$為字符串聯(lián)接，j＝1，2，…，L，n是集合Ω數(shù)據(jù)的個數(shù)；

用b個均勻散列的哈希函數(shù)將bitgroup_y，j散列為b個[1，m]地址，定義為：f₁(bitgroup_y，j)，f₂(bitgroup_y，j)，…，f_b(bitgroup_y，j)

將HLBF[f₁(bitgroup_y，j)]，HLBF[f₂(bitgroup_y，j)，…，HLBF[f_b(bitgroup_y，j)]置1，

對于給定查詢數(shù)據(jù)Q，通過隨機翻轉(zhuǎn)Q上s個比特生成c個虛擬對象：Q^(x)，x＝1，2...，c，對于每一個虛擬數(shù)據(jù)Q^(x)，生成L個位串，即bitgroup_Q(x)，j＝j(luò)$Q^(x)[h_1，j]＄Q^(x)[h_2，j]＄…$Q^(x)[h_k，j]，j＝1，2，…，L，

若一個位串在布隆過濾器HLBF中的b個地址的比特位都為1，則稱該位串通過，如L組bitgroup_Q(x)，1，bitgroup_Q(x)，2，…，bitgroup_Q(x)，j中任意一組通過，x＝1，2...，c，則Q是集合Ω的近似成員。