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 条评论
登录 后参与评论

相关文章

来自专栏程序员宝库

用 PHP 的方式实现的各类算法合集

项目地址: https://github.com/PuShaoWei/arithmetic-php About 如果说各种编程语言是程序员的招式,那么数据结构和...

3626
来自专栏数据结构与算法

2017.10.23解题报告

预计分数:100+60+0=160 实际分数:100+80+0=180 T1 题目描述 现在有一个字符串,每个字母出现的次数均为偶数。接下来我们把第一次出现的字...

3035
来自专栏有趣的Python

15-数据结构探险系列-图篇数据结构探险之图篇

图的存储结构:邻接矩阵(数组);邻接表(链表)有向; 十字链表(链表)有向;邻接多重表(链表)无向

773
来自专栏C语言及其他语言

[每日一题]矩阵乘法

本次的题目来源于C语言网比赛栏目八月月赛第一题,记得去试试看看自己能不能AC哦!!! 题目描述 给定一个N阶矩阵A,输出A的M次幂(M是非负整数) 例如: ...

3165
来自专栏落影的专栏

程序员进阶之算法练习(十四)

前言 坚持做算法练习对开发的好处是抽象能力变强,拿到一个需求能很快对其进行抽象,然后再用学过的设计模式相关知识进行整理,最后用代码实现。 最大的好处在于:对...

3347
来自专栏zaking's

用js来实现那些数据结构16(图02-图的遍历)

1103
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之从1到n中出现1的次数(九度OJ1373)

题目描述: 亲们!!我们的外国友人YZ这几天总是睡不好,初中奥数里有一个题目一直困扰着他,特此他向JOBDU发来求助信,希望亲们能帮帮他。问题是:求出1~13的...

18610
来自专栏tkokof 的技术,小趣及杂念

小聊聊NGUI中Panel的Clip功能(之一)

  首先来看顶点着色器(即vert),前几行都比较传统:使用ModelViewProjection来变换顶点,然后设置顶点颜色和纹理坐标,只是最后一步有些奇怪:

442
来自专栏数据小魔方

excel函数入门须知——绝对引用与相对引用

今天给大家讲解excel函数入门必备知识——绝对引用与相对引用! ▽ 别怪小魔方大过年的污染大家心情 不知道是哪根筋不对 就是这么勤劳、敬业 今天给大家讲解ex...

2736
来自专栏瓜大三哥

形态学滤波(五)

形态学滤波(五) 之一维形态学腐蚀/膨胀子模块设计 对于图像处理而言,是纵向和横向两个维度的处理。我们知道,对于任何二维的操作,都可以分解为一维方向的操作来简化...

2056

扫码关注云+社区