python - BloomFilter Python

我是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。基本上，index1是hash的前两个字节的串联，而index2是hash的后两个字节的串联。

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

这两行截断了值，以使它们不会超出bloom可能的索引范围。 %是mod运算符；它在除法后返回余数。 (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...

并且，如果对特定的i.p.进行哈希处理时，生成的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(可以使用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 - BloomFilter Python，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9026519/