布隆过滤器 Python

Question

我刚开始学习Python，想要根据BitTorrent的BEP 33来创建一个布隆过滤器（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')

Answer 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中的索引。简单来说，index1是哈希值前两个字节拼接而成的，index2是哈希值第二个两个字节拼接而成的。

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

这两行代码将值截断，以确保它们不会超过bloom的索引范围。%是取模运算符；它返回除法后的余数。（例如，17 % 4 = 1，22 % 5 = 2，依此类推。）记得bloom是256 * 8位长吗？11位可以编码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...

如果某个特定的IP在哈希后生成了index1为5和index2为9，那么它就会被认为“在”过滤器中，因为索引5和9的位被设置为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(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')