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 会将其编码成：

对于一次查询来说，首先会在 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）。

对于 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。

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。