IT博客汇
  • 首页
  • 精华
  • 技术
  • 设计
  • 资讯
  • 扯淡
  • 权利声明
  • 登录 注册

    Golomb-coded sets 原理介绍

    JerryQu 的小站发表于 2015-11-16 08:54:53
    love 0

    在我之前的《H2O 中的 Cache-Aware Server Push 简介》这篇文章中,我写到:

    H2O 将要推送的资源路径 + ETag 存入一个集合,采用 Golomb-compressed sets 算法生成指纹,并编码为 Base64 字符串存入 Cookie,之后 H2O 可以通过检查某个资源路径 + ETag 是否存在于 Cookie 指纹对应的集合之中来决定是否推送。

    Golomb-compressed sets(GCS)是一种空间利用率很高的数据结构,可以用于判断一个元素是否属于这个集合。它与 Bloom Filter 非常类似,区别是它的压缩率更高,同时查询效率更低。同样,GCS 也有将原本不属于集合的元素误判为属于的可能(false positive)。

    H2O 将 GCS 算法用在记录 Push 过的资源集合非常合理:Cookie 往返于客户端和服务端之间,需要尽可能小;而需要 Push 的资源数量通常不多,即使查询效率低一点也无大碍;同时 Server Push 属于锦上添花的功能,允许有一定的误判。

    GCS 的实现原理并不复杂,本文试图用最简单的语言带领大家认识一下它。本文属于科普性质,给出的代码仅作示意,要在实际项目中使用 GCS,请参考本文最后给出的开源库。

    HASH

    首先定义一个数组集合,将它的长度记为 N。允许的误判率记为 1/P,本文假定 P=64,表示允许 1/64 的误判率。这部分准备工作的代码如下:

    var encoded_words = ['alpha', 'bravo', 'charlie', 'delta', 'echo', 'foxtrot', 'golf', 'hotel', 'india', 'juliet', 'kilo', 'lima', 'mike', 'november', 'oscar', 'papa', 'quebec', 'romeo', 'sierra', 'tango', 'uniform', 'victor', 'whiskey', 'xray', 'yankee', 'zulu'];
    var N = encoded_words.length;
    var P = 64;
    

    接着,将数组每一项都映射为范围在 [0, N * P) 之间的整数。为了让映射后的数字尽可能均匀分布,需要借助 MD5、SHA-1 等 Hash 函数。本文使用 MD5 实现映射函数:

    function gcs_hash(str, N, P) {
        var h = md5(str);
        return parseInt(h.substring(24, 32), 16) % (N * P);
    }
    

    将前面数组的每一项都进行 gcs_hash 处理:

    var hashResult = encoded_words.map(function(word) { return gcs_hash(word, N, P) });
    

    运行这段代码,得到如下结果:

    [1017, 591, 1207, 151, 1393, 1005, 526, 208, 461, 1378, 1231, 192, 1630, 1327, 997, 662, 806, 1627, 866, 890, 1134, 269, 512, 831, 1418, 1525]
    

    这样,N 个不定长的字符串被映射成为 N 个取值在 [0, N * P) 之间的整数了。

    要检测一个元素是否在集合内,只需将待检测的元素以相同的 N、P 参数调用 gcs_hash,通过检查 Hash 后的结果是否在前面算好的 Hash 数组即可。例如:

    gcs_hash('apple', N, P) // 1535,1535 不在 Hash 数组内,故 apple 不在集合内。
    

    显然,对于集合中存在的元素,Hash 值一定会在 Hash 数组内;但 Hash 值在 Hash 数组内的元素,并不一定在集合内,因为元素到 Hash 值是多对一的映射关系。

    压缩

    现在我们手头上已经有了一个可以用于检测的 Hash 数组,剩下的工作就是如何压缩它了。

    将数组从小到大排序,如果 Hash 结果分布足够均匀,N 个取值为 [0, N * P) 的元素,相邻两者差值一定接近于 P。我们画出图表看一下:

    hash-data-sorted

    上图中蓝线是 Hash 数组的各个点,黄线是 64 的倍数,可以看到二者基本能吻合。

    接着,保留数组第一项,并将后续每一项都改为与前一项的差值(差值为 0 的情况直接跳过),这样数组每一项都比较接近 64 了。代码示意如下:

    hashResult.sort(function(a, b) { return a -b });
    
    var diffResult = [hashResult[0]];
    for(var i = 0; i < N - 1; i++) {
        var diff = hashResult[i+1] - hashResult[i];
        if(diff === 0) {
            continue;
        }
        diffResult.push(diff);
    }
    

    这段代码运行结果如下:

    [151, 41, 16, 61, 192, 51, 14, 65, 71, 144, 25, 35, 24, 107, 8, 12, 117, 73, 24, 96, 51, 15, 25, 107, 102, 3]
    

    GCS 使用了 Golomb encoding(哥伦布编码)对上述数组做进一步处理。哥伦布编码是一个针对整数的变长编码方式,详细介绍可以看维基百科。这里简单介绍下:

    哥伦布编码使用指定的整数 M 把输入的整数分成两部分:商数 q、余数 r。 商数当做一元编码,而余数放在后面做为可缩短的二进制编码。

    将整数变为一元编码非常简单:q 的一元编码结果就是 q 个 1 加上 1 个 0。如下表:

    整数 一元编码
    0 0
    1 10
    2 110
    3 1110
    4 11110
    5 111110
    6 1111110

    一元编码可以用以下代码实现;

    function unary_encoding(q) {
        return 1 << (q + 1)) - 2;
    }
    

    将 M 选为 64 时,余数取值区间为 [0, 64),只需要用 6 位二进制表示。将待处理的数组每一项都除以 64,并将商数和余数分别做一元编码和二进制编码,得到如下结果:

    整数 商数 余数 商数一元编码 余数二进制编码
    151 2 23 110 010111
    41 0 41 0 101001
    16 0 16 0 010000
    61 0 61 0 111101
    192 3 0 1110 000000
    51 0 51 0 110011
    14 0 14 0 001110
    65 1 1 10 000001
    71 1 7 10 000111
    144 2 16 110 010000
    25 0 25 0 011001
    35 0 35 0 100011
    24 0 24 0 011000
    107 1 43 10 101011
    8 0 8 0 001000
    12 0 12 0 001100
    117 1 53 10 110101
    73 1 9 10 001001
    24 0 24 0 011000
    96 1 32 10 100000
    51 0 51 0 110011
    15 0 15 0 001111
    25 0 25 0 011001
    107 1 43 10 101011
    102 1 38 10 100110
    3 0 3 0 000011

    表格中每一行后两列拼起来就是该整数对应的哥伦布编码,可以看到,64 以下的整数编码后会变短。这部分代码实现如下:

    function golomb_enc(arr, P) {
        return arr.map(function(n) {
            var q = n / P | 0;
            var r = n % P;
    
            return ((1 << (q + 1)) - 2).toString(2) + (r + P).toString(2).slice(1);
        });
    }
    
    var golombResult = golomb_enc(diffResult, P);
    

    这段代码运行结果如下:

    ["110010111", "0101001", "0010000", "0111101", "1110000000", "0110011", "0001110", "10000001", "10000111", "110010000", "0011001", "0100011", "0011000", "10101011", "0001000", "0001100", "10110101", "10001001", "0011000", "10100000", "0110011", "0001111", "0011001", "10101011", "10100110", "0000011"]
    

    最终结果有 197 位,25 个字节:

    11001011 10101001 00100000 11110111
    10000000 01100110 00111010 00000110
    00011111 00100000 01100101 00011001
    10001010 10110001 00000011 00101101
    01100010 01001100 01010000 00110011
    00011110 01100110 10101110 10011000
    00011
    

    理论上,要实现单元素 1/64 的误判率最少只需要 6 位,26 个元素就是 156 位。GCS 的编码结果比理论值大了 26.3%,但仍优于 Bloom Filter。实际使用中,为了考虑解码通用性,一般会将 N 和 P 按照约定好的长度进行编码,追加到最终结果的开始。编码结果最后不足一字节的部分也需要补全,所以还会有一些额外开销。但是 N 和 P 越大,最终编码长度就越接近于理论值。H2O 默认使用的 P 是 8192(2^13)。

    查询时,只需要将上述步骤倒过来得到 Hash 数组即可,这里不在赘述。由于 Hash 数组分布比较均匀,可以将它分为多个区间来提高查询效率。

    参考:

    • Golomb Coded sets 的 C++、Python、JS 实现(Github)
    • Golomb-coded sets: smaller than Bloom filters

    本文链接:https://imququ.com/post/golomb-coded-sets.html,参与讨论

    推荐:领略前端技术 阅读奇舞周刊



沪ICP备19023445号-2号
友情链接