这个过滤器本身是一篇论文中提出的过滤器的简化版本,去掉了计数功能,我觉得简化版本应用的可能也很广,专门写一篇简化版本的RSQF。RSQF全称是rank-and-select based filter,一会我们会专门来讲这个rank-and-select是什么。 原论文可以到这里下载:http://www3.cs.stonybrook.edu/~ppandey/files/SIGMOD17_Talk_CQF_long.pdf

过滤器分下面几部分来讲

Hash函数

这部分不属于原论文,这部分假设有一个比较好的Hash函数,可以将原数据hash成n位数据,设n = q + r,这个r实际上控制着过滤器的假阳率和空间大小的平衡。假阳率是$2^{-r}$,当然如果r越大,空间消耗也越大

结构

结构部分如下图所示 image1

我们分别来介绍这个结构中的各部分,其中occupieds这一行是1bit数组,元素只能表示1或0;runends也是1bit数组;remainders内每个元素占用r个bit,就是前一部分说的r。这个块总共有$2^q$列,q也是前文说的q。

我们设某一列的下标为$i$,则当有元素hash后的前q位对应到这一列的时候,$occupieds[i] = 1$;我们把这个元素放到对应位置上,那么如果有多个元素对应这个位置,我们要求,把具有相同前q位的元素放到相邻位置。那么什么时候代表结束呢?就是这些前q位相同的元素的最后一个元素对应位置$runends[i] = 1$。在图中,相同颜色的元素其前q位是相同的,也就是说如果不考虑重复,他们都应该存在相同位置上的。

算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def MAY_CONTAIN(Q,x)
"""
查找算法,Q代表存储结构,x代表要查找的元素
"""
    b = h0(x) #计算hash值,取其前q位
    if Q.occupieds[b] = 0:
        return 0
    t = RANK(Q.occupieds,b)
    k = SELECT(Q.runends,t)
    v = h(x) #计算hash值取其后r位
    while k >= b and Q.runends[k] = 0:
        if Q.remainders[k] = v:
            return 1
        k -= 1
    return false

RANK(Q,i)是找到在位置i之前,数组Q中有多少个1出现过 SELECT(Q,i)是找到数组Q中第i次出现1的位置

先通过找到在某个位置之前在occupieds上有多少个1,就代表有多少组相同前q位hash值的元素组,然后通过runends的第i个1,找到目前这个位置对应的组,这样就可以精准定位。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def find_first_unused_slot(Q,x):
    """
    找到第一个空位置,以便于在插入元素时向后移动元素
    """
    r = rank(Q.occupieds,x)
    s = select(Q.runends)
    while x < s:
        x = s + 1
        r = RANK(Q.occupieds,x)
        s = SELECT(Q.runends,s)
    return x
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def insert(Q,x):
    """
    插入一个元素
    实质是先找到一个空位,然后把要插入位置之后的所有元素依次右移,直到把要插入位置空出来为止
    """
    r = RANK(Q.occupieds,h0(x))
    s = SELECT(Q.runends,r)
    if h0(x) > s:
        Q.remainders[h0(x)] = h1(x)
        Q.runends[h0(x)] = 1
    else:
        s += 1
        n = find_first_unused_slot(Q,s)
        while n > s:
            Q.remainders[n] = Q.remainers[n-1]
            Q.runends[n] = Q.remainers[n-1]
            n -= 1
        Q.remainers[s] = h1(x)
        if Q.occupieds[h0(x)] == 1:
            Q.runends[s-1] = 0
        Q.runends[s] = 1
        Q.occupieds[h0(x)] = 1
    return

原论文中其实还有一个在块内加速的一个索引方式,在这里没有讲到,想要详细了解的可以看原论文。如果想要看带计数功能版本的过滤器也请看原论文,github上也有公开代码。https://github.com/splatlab/cqf