gpt4 book ai didi

python - 布隆过滤器 Python

转载 作者:太空狗 更新时间:2023-10-30 02:49:17 28 4
gpt4 key购买 nike

我是 python 的新手,正在尝试创建一个基于 Bit torrent BEP 33 的 bloomFilter。我已经创建了 Bloom Filter,但它并不是我想要的。这是我需要的,我还没有完全理解这种情况。如果这里有人可以解释...

//fixed parameters

k = 2

m = 256*8

//the filter
byte[m/8] bloom ## What is this part?

function insertIP(byte[] ip) {

byte[20] hash = sha1(ip)

int index1 = hash[0] | hash[1] << 8
int index2 = hash[2] | hash[3] << 8

// truncate index to m (11 bits required)
index1 %= m ## ?
index2 %= m ## ?

// set bits at index1 and index2
bloom[index1 / 8] |= 0x01 << index1 % 8 ## ??
bloom[index2 / 8] |= 0x01 << index2 % 8 ## ??
}

// insert IP 192.168.1.1 into the filter:
insertIP(byte[4] {192,168,1,1})

这是我创造的

import hashlib
m = 2048
def hashes(s):
index = [0, 0]
#for c in s:
#o = ord(c)
index[0] = hashlib.sha224(index[0]).hexdigest ## This needs integer hash
index[1] = hashlib.sha224(index[1]).hexdigest ## same as above

return [x % m for x in index]

class BloomFilter(object):
def __init__(self):
self.bitarray = [0] * m

def add(self, s):
for x in hashes(s):
self.bitarray[x] = 1
#print self.bitarray
def query(self, s):
return all(self.bitarray[x] == 1 for x in hashes(s))

shazib=BloomFilter()
shazib.add('192.168.0.1')
print shazib.query('192.168.0.1')

最佳答案

首先,代码的解释......

//fixed parameters

k = 2

这是我最困惑的一句话; k 根本没有使用...

m = 256*8

这是 256 字节中的位数。

//the filter
byte[m/8] bloom ## What is this part?

bloom 是一个 256 字节的数组,即 256 * 8 位,即 m 位。 bloom 中的每一位都将包含有关过滤器中的值的信息。

function insertIP(byte[] ip) {

byte[20] hash = sha1(ip)

这会创建一个 20 字节的 ip 散列。

    int index1 = hash[0] | hash[1] << 8
int index2 = hash[2] | hash[3] << 8

这两行根据哈希将两个索引计算到 bloom 中。基本上,index1hash 前两个字节的串联,index2hash 后两个字节的串联

    // truncate index to m (11 bits required)
index1 %= m ## ?
index2 %= m ## ?

这两行截断值,以便它们不会超出 bloom 中可能的索引范围。 % 是模运算符;它返回除法后的余数。 (17 % 4 = 1、22 % 5 = 2 等等。)还记得 bloom 的长度是 256 * 8 位吗?十一位允许我们编码 2 ** 11 个可能的索引,即 2048 个值,即 256 * 8 个值。

    // set bits at index1 and index2
bloom[index1 / 8] |= 0x01 << index1 % 8 ## ??
bloom[index2 / 8] |= 0x01 << index2 % 8 ## ??

我们将 bloom 视为一个位数组,因此我们必须进行一些位运算才能访问正确的位。首先,将 indexA 除以 8,以获得正确的字节,然后使用 % 运算符截断 indexA 以获得该字节中的正确位。

}

// insert IP 192.168.1.1 into the filter:
insertIP(byte[4] {192,168,1,1})

瞧,我们有一个布隆过滤器。如果按位打印出来,它看起来像这样:

data->    001011000101110011000001001000100...

indices-> 000000000011111111112222222222333...
012345678901234567890123456789012...

如果一个特定的 i.p. 在被散列时生成 5index19index2 ,则它将被视为“在”过滤器中,因为索引 59 处的位被设置为 1。当然,可能存在误报,因为多个不同的值可能会导致相同的索引;但不能有漏报。

import hashlib
m = 2048
def hashes(s):
index = [0, 0]
#for c in s:
#o = ord(c)
index[0] = hashlib.sha224(index[0]).hexdigest ## This needs integer hash
index[1] = hashlib.sha224(index[1]).hexdigest ## same as above

这是您的第一个问题。 index[0]index[1] 必须是整数。此外,hashlib.sha224(index[0]).hexdigest 返回一个方法。您必须调用该方法才能从中获取任何信息,例如:hashlib.sha224(index[0]).hexdigest()。此外,如果您希望它以与上述代码相同的方式工作,您可以将散列转换为 int(您可以使用 int(x, 16) 将十六进制字符串转换为整数)然后使用& 65535提取前两个字节,然后使用>> 16将其移动两个字节,然后使用& 65535<提取这两个字节 再次。一旦你弄对了,剩下的就可以了。

    return [x % m for x in index]

class BloomFilter(object):
def __init__(self):
self.bitarray = [0] * m

def add(self, s):
for x in hashes(s):
self.bitarray[x] = 1
#print self.bitarray
def query(self, s):
return all(self.bitarray[x] == 1 for x in hashes(s))

shazib=BloomFilter()
shazib.add('192.168.0.1')
print shazib.query('192.168.0.1')

关于python - 布隆过滤器 Python,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9026519/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com