SuRF: 一个优化的 Fast Succinct Tries

作者:唐刘

在前一篇文章中,我简单介绍了 Succinct Data Structure,这里我们继续介绍 SuRF。

Fast Succinct Tries

SuRF 的核心数据结构就是 Fast Succinct Tries(FST),一种空间节省,支持 point 和 range query 的静态 trie。在很多时候,对于一棵树来说,上层的 trie 节点较少,但访问频繁,也就是我们俗称的 hot,而下层的节点则相对的 cold 一点。因此,SuRF 使用了两种数据结构来分别处理 hot 和 cold 节点。在 upper 层上面使用了 LOUDS-Dedense,而在 lower 层上面使用 LOUDS-Sparse。

对于一个 trie 来说,SuRF 会将其编码成:

image

对于一次查询来说,首先会在 LOUDS-Dense 上面查找,如果找到了,就直接返回,找不到,就会进入到 LOUDS-Sparse 进行查找。

LOUDS-Dense

LOUDS-Dense 对于每个 Node 都使用了三个 256 bit 大小的 bitmap。第一个 bitmap 叫做 D-labels,如果表示这个 node 是否有 label i,如果有,那么第 i bit 位就是 1。譬如上面的例子,Dense 的 label 在 level 1 有 f,s 和 t,那么在第 102(f),115(s) 和 116 (t)bit 位就会设置为 1。大家其实可以看到,具体哪一个 bit 位,就是 ASCII 码的值。

第二个 bitmap 是 D-HasChild,如果一个 node 下面还有子节点,那么就将该 label 对应的 bit 在 D-HasChild 里面设置为 1。继续上面的例子,f 和 t 都有子节点,而 s 没有,所以 102 和 116 bit 都会设置为 1。

第三个 bitmap 是 D-IsPrefixKey,这个解释其实有点绕,主要是用来表示一个 prefix 是否也是一个合法的 key。还是上面的例子,我们可以看到,f 这个 node 是有子节点的,所以它是一个 prefix,但同时,f 也是一个 key。在上图中, SuRF 使用了 ‘$’ 这个符号(实际对应的值是 0xFF)来表示这样的情况。

最后一个字节序列就是 D-Values,存储的是固定大小的 value。Value 就是按照 每层 level 的顺序存放的。

如果要进行遍历 LOUDS-Dense,我们可以使用之前提到的 rank 和 select 操作。对于 bit 序列 bs 来说,我们用 rank1/select1(bs, pos) 来表示在 bs 上面 pos 的 rank 和 select 操作。譬如,假设 pos 是 D-Labels 上面的当前 bit pos,如果 D-HasChild[pos] = 1,那么第一个子节点的 pos 则是 D-ChildNodePos(pos) = 256 x rank1(D-HasChild, pos),而父节点则是 ParentNodePos(pos) = 256 x select1(D-HasChild, pos / 256)

LOUDS-Sparse

不同于 LOUDS-Dense,LOUDS-Sparse 使用了 bytes 或者 bits 序列来编码。第一个 bytes 序列,S-Labels,按照 level order 的方式记录了所有 node 的 label。譬如上图的 rst 这样的 bytes 顺序,Sparse 仍然使用了 0xFF(也就是上图的 $ 符号)来表示一个 prefix key。因为这样的 0xFF 只会出现在第一个子节点上面,所以是能跟实际的 0xFF label 进行区分的。

第二个 bit 序列就是 S-HasChild, 这个跟 D-HasChild 差不多,就不解释了。

第三个 bit 序列 S-LOUDS 用来表示,如果一个 label 是第一个节点,那么对应的 S-LOUDS 就设置为 1,否则为 0。譬如上图第三层,r,p 和 i 都是第一个节点,那么对应的 S-LOUDS 就设置为 1 了。

最后一个 bytes 序列是 S-Values,跟 D-Values 类似,不再解释了。

如果要便利 Sparse,也是通过 rank 和 select 进行,譬如找到第一个子节点 S-ChildNodePos(pos) = select1(S-LOUDS, ranks(S-HasChild, pos) + 1),而找到父节点则是 S-ParentNodePos(pos) = select1(S-HasChild, rank1(S-LOUDS, pos) - 1)

Optimization

对于 SuRF 来说,为了提高查询的速度,一个重要的优化手段就是提高 rank 和 select 执行的效率,在 SuRF 里面,引入了 LookUp Table(LUT)。

image

对于 rank 来说,会将 bit vector 切分成 B bits 大小的块,每块都使用 32 bits 的字段来预先保存了计算好的到这个 block 的 rank 值。譬如,在上面的例子,第三个就是 7,保存的就是前两个 block 总的 rank 数量。

而对于一个 pos 来说,它的 rank1(pos) = LUT[i / B] + popcount[i / B * B, i]popcount 是一个 CPU 指令,用来快速的计算某一段区间的 1 的个数。假设我们现在要得到 pos 12 的 rank 值,先通过 LUT[12 / 5] = LUT[2] = 7,然后得到 range [12 / 5 * 5, 12] = [10, 12],使用 popcount 得到 2,那么 12 的 rank 就是 9。

对于 select 来说,也是使用的 LUT 方法,预先记录算好的值。具体到上面,假设将采样的周期设置为 3,那么第三个 LUT 就保存的是 3 x 2,也就是第 6 的 1 的 pos 值,也就是 8。对于一个 pos 来说,select1(i) = LUT[i / S] + (selecting (i - i / S * S)th set bit starting from LUT[i / S] + 1) + 1。譬如,如果我们要得到 select1(8),首先得到 LUT[8 / 3] = LUT[2] = 8,然后需要从 position LUT[8 / 3] + 1 = 9 这个位置,得到第 (8 - 8 / 3 * 3) = 2 个位置的 bit,也就是 1,所以 select1(8) 就是 10。

当然,SuRF 还有其它很多优化手段,譬如使用 SIMD 来提速 label 的查找,使用 prefetchj 技术等,这里就不说明了。

Succinct Range Filter

对于通常的 SuRF 来说,它因为对这个 trie 都进行了编码,所以它是完全精确的,虽然它是一种省空间的数据结构,但很多时候,我们仍然需要能保证在内存里面存储所有的 SuRF 数据,所以我们就需要对 SuRF 进行裁剪,不存储所有的信息,也就是说,我们需要在查询的 False Positive Rate(FPR)和空间上面做一个权衡。

在 SuRF 里面,有几种方式,Basic,Hash,Real 以及 Mixed。

image

Basic 比较简单,就是直接将最后面的叶子层全部砍掉,这样其实是最省空间的,但 FPR 会比较高。Hash 的方式,则是在最底层,保存了这个 key n bits 位的 hash 值,这样能显著减少 point get 的 FPR,但对于 range 操作则没有任何帮助。

为了解决 Hash range 查询的问题,也可以使用 Real 方式,在最后面继续保存 n bits 位的 key 数据。Real 虽然能处理 point get 和 range,但它的 FPR 其实是比 Hash 要高的。所以我们可以使用 Mixed 方式,将 Hash 和 Real 混合在一起使用。

Example

SuRF 的代码已经开源,大家可以自己从 Github 获取到,使用起来也非常的简单,下面是一个非常简单的例子:

vector<string> words = {
 "f",
 "farther",
 "fas"
 "trying"
};

SuRF s(words, true, 16, kNone, 0, 0);

cout << "Find abc " << s.lookupKey("abc") << endl;
cout << "Find trying " << s.lookupKey("trying") << endl; 

上面我创建了一个 SuRF,传入了一批 words,使用了 Full Trie 的模式,然后做了两次点查。

具体代码,大家可以自己去研究下,代码质量还是很不错的。

Epilogue

SuRF 的研究就暂时到这里结束了,对于 Succinct Data Structure,我个人还是觉得很有意思,可以探究的东西挺多的,毕竟如果能把查询索引全放在内存,不走磁盘,性能还是非常不错的。但我个人毕竟水平有限,仅仅限于了解,所以特别希望能跟业界的大牛多多交流。如果你也对这块很感兴趣,欢迎联系我 tl@pingcap.com。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏JavaEdge

亿万级数据处理的高效解决方案简介从set/map到hashtable/hashmap/hashset秘技一:分而治之/Hash映射 + HashMap统计 + 堆/快速/归并排序堆秘技二:双层桶划分秘

1.4K70
来自专栏程序员的酒和故事

跟Google学写代码--Chromium工程中用到的C++11特性

Ttile 跟Google学写代码--Chromium工程中用到的C++11特性 Chromium是一个伟大的、庞大的开源工程,很多值得我们学习的地方。 《跟...

46640
来自专栏微服务生态

由学习《软件设计重构》所想到的代码review(二)

我们接第一篇来继续说明在代码review中,有哪些属于“层次结构”中的坏味道。 第一篇链接如下:http://www.jianshu.com/p/07dbf6...

9620
来自专栏用户2442861的专栏

数据库系统——B+树索引

http://blog.csdn.net/cjfeii/article/details/10858721

51910
来自专栏冰霜之地

如何设计并实现一个线程安全的 Map ?(上篇)

Map 是一种很常见的数据结构,用于存储一些无序的键值对。在主流的编程语言中,默认就自带它的实现。C、C++ 中的 STL 就实现了 Map,JavaScrip...

32720
来自专栏前端笔记

【 数字游戏 2048 】原生 JavaScript 做小游戏

原生 JavaScript 2048 源码 : <!doctype html> <html> <head> <title>2048</title> <m...

442130
来自专栏蘑菇先生的技术笔记

探索C#之布隆过滤器(Bloom filter)

33850
来自专栏猿人谷

面试必备:HashMap、Hashtable、ConcurrentHashMap的原理与区别

HashMap和Hashtable都是用hash算法来决定其元素的存储,因此HashMap和Hashtable的hash表包含如下属性:

21910
来自专栏北京马哥教育

hiphop原理分析1

Hiphop是Facebook开发一款PHP二进制化的一个工具,最开始是由php转为C++,但是后来发现编译为c++的话,许多的时间会花费在编译代码上面,调试不...

32170
来自专栏用户2442861的专栏

STL deque源码实现及分析

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/d...

54520

扫码关注云+社区

领取腾讯云代金券