本文介绍一个压缩前缀树实现的(sorted set(github:succinct.Set [1])区区 95 行代码,包含了一组完整的功能:
loc100 分支是本文中使用的最简实现,没有任何外部依赖,main 分支中的实现面向生产环境,要快 4 倍左右。
succinctSet 空间开销是源数据的 57%。
Has() 开销为 350 ns。
Data | Engine | Size(KB) | Size/original | ns/op |
---|---|---|---|---|
200kweb2 | bsearch | 5890 | 267% | 229 |
200kweb2 | succinct.Set | 1258 | 57% | 356 |
200kweb2 | btree | 12191 | 553% | 483 |
生产环境中使用的算法,和本文介绍的方法同源,但包括更多的优化,例如通过 SIMD 指令一次处理多个字节的比较,用 bitmap 来优化 labels 的存储,对只有一个出向 label 的节点的合并优化等。
^
是 root 节点(也记做0),1, 2, 3…是 trie 节点,$
标记一个叶子节点,字母 a, b...
表示一个节点到下级节点的边(labeled branch):^
,或 1, 2, 3。
也可以是叶子节点,例如 3, 6, 9。
这里 3 既是一个 inner 节点也是一个 leaf 节点。要压缩这个 trie,对每个 trie 节点,我们需要的最核心的信息是:
一个节点的分支(label)都有哪些,
以及 label 指向的节点的位置。
我们有以下这种紧凑的结构来描述这个 trie:
一个 trie 节点的出向 label 都存储在一个 []byte 中,再用一个 bitmap 来描述每个节点的分支,后面通过这个 bitmap 来定位 label 对应的节点。
先把每个节点对应的 label 列出来,并为每个 label 分配一个bit 0 来标记:
然后将所有的 label 保存在一个 []byte 中,再将对应的标记 label 的多个 0... 用 1 做分隔符连接到一起:这 2 块信息是 succinctSet 核心的 2 个字段,有了这 2 部分数据就可以实现(不算高效的)key 查找:
y-> ⑦ $
:^
,每个节点都有一个 0
与之对应(节点入向 label 对应位置的0)。 图中上下箭头,是 label 到节点的关系,也就是每个 0
跟它指向的子节点的对应关系。1
与之一一对应,也就是每个节点都有一个结束标记 1
。0
对应节点 1:bx
,第 1 个 0
对应节点 2:u
…1
的关系也类似,第 0 个 1
对应 root 节点 ^
,0:ab,
第 1 个 1
对应节点 1:bx
,第 2 个 1
对应节点 2:u
…0,
例如是第 i 个0
,再找到 bitmap 中的第 i 个 1
,第 i 个 1
后面就是 label 对应的节点位置了。0:ab
中找到 label a
,a
对应第 0 个 0
,然后找到第 0 个 1
的位置,也就是 1:bx
节点。1:bx
节点的 label 中找到 label x
,对应第 3 个 0
,再找到第 3 个 1
的位置,也就是 4:y
的节点。4:y
中找到 label y
,对应第 7 个 0,
再找到第 7 个 1,
也就是 7:ø
的节点。6:d
,它本身有一个出向分支 d
,是一个 inner 节点,同时也是一个 leaf 节点。i
个 bit 为 1
,表示 node-id 为 i
的节点是 leaf 节点:0
的个数 i,再找到第 i 个的 1
的位置。这 2 个操作都是 O(n) 的,要遍历 bitmap,最终会导致一次查询的时间效率变成 O(n²)。i
个 bit 之前有多少个 1(或多少个 0
),
对定长整数,例如一个 uint64,它的有 O(1) 的实现,例如bits.OnesCount64()
这个函数,数数一个 uint64 里有多少个 1;i
个 1 的位置的操作,叫做 select1(i)。rank []int32
:ranks[i]
记录 bitmap 中前 i*64
个 bit 中的 1
的数量。. 这样要计算 rank(i) 就只需要取 ranks[i/64],再用一个 O(1) 的函数调用(如 bits.OnesCount64()
)计算 bitmap[i:i % 64]
中的 1 的个数。[]int32
: select[i]
记录第 i*32
个 1
在 bitmap 中哪个位置。1
在第 1 个 bit,第 32 个 1
在第 67 个 bit,第 64 个 1
出现在第 126 个 bit,那么 selects 的索引就是:[1, 67, 126]
:1(或 0
)
的数量就可以确定用 O(1) 时间完成;而 select 索引,可以尽可能让找出第 i 个 1 的开销趋近于 O(1);因为 selects 的 2 条索引之间可能跨越几个 uint64,取决于 bitmap 中 1
的分布。我们接下来看看完整的代码逻辑:
keys = [ab, abc, abcd, axy, buv]
为例,来描述 Set 的建立,^
的出向分支,有 2 个 label: a,b
a
和前缀为 b
拆分成 2 部分,顺次放到队列尾部等待处理。.a
的 keys,扫描这些 keys 的第 2 列,找到节点 1
的出向 label: b,x
a
的集合拆分为前缀为 ab
的集合和前缀为 ax
的集合,顺次放到队列尾部等待处理。b
的 key 集合的第 2 列,找到 1 个出向 label u,
把所有前缀为 bu
的 key 放到队列尾部等待处理。init()
给建好的 trie 做 rank 和 select 的索引。select1(rank0(i))
的方法走到下一个节点,继续以上步骤。rank0(i)
,以及找出第 i 个 1 的位置:select1(i)
。1
的 bit 数。我们用它来给 bitmap 中每个 unit64 提前计算好前面有几个 1
,这样在使用的时候只需要再处理最后一个 uint64 就可以了。1
的个数,然后在个数满 32 整数倍时添加一条索引。0
时,通过 rank0(i) = i - rank1(i)
来计算:1
所在位置时,我们先通过 selects 索引找到一个最接近的 uint64,再向后逐个查找直到见到第 i 个 1
。这一步的性能不是严格的 O(1):Data | Engine | Size(KB) | Size/original | ns/op |
---|---|---|---|---|
200kweb2 | bsearch | 5890 | 267% | 229 |
200kweb2 | succinct.Set | 1258 | 57% | 356 |
200kweb2 | btree | 12191 | 553% | 483 |
Data | Engine | Size(KB) | Size/original | ns/op |
---|---|---|---|---|
870k_ip4_hex | bsearch | 17057 | 500% | 276 |
870k_ip4_hex | succinct.Set | 2316 | 67% | 496 |
870k_ip4_hex | btree | 40388 | 1183% | 577 |
[1]
succinct.Set : https://github.com/openacid/succinct/tree/loc100[2]
slim: https://github.com/openacid/slim[3]
google btree : https://github.com/google/btree[4]
前缀树: https://en.wikipedia.org/wiki/Trie[5]
popcount : https://en.cppreference.com/w/cpp/numeric/popcount[6]
zipf: https://blog.openacid.com/tech/zipf/[7]
report : https://github.com/openacid/succinct/blob/v0.1.0/report/main.go
Databend 文档:https://databend.rs/
Twitter:https://twitter.com/Datafuse_Labs
Slack:https://datafusecloud.slack.com/
Wechat:Databend
GitHub :https://github.com/datafuselabs/databend