0
100行代码的压缩前缀树: 50% smaller
这文介绍一个压缩前缀树实现的sorted set(github:succinct.Set), 区区95行代码, 包含了一组完整的功能:
用前缀树存储一个排序数组, 去掉指针, 压缩掉50%的空间; 例如在本文的例子中, 存储2.4MB的200万个单词, 只需要1.2MB.
创建: 从key列表创建一个压缩的前缀树;
查询: 支持Has() 操作来查询1个key是否存在;
优化: 通过索引来加速 bitmap 的操作, 将较大的 bitmap 操作优化到O(1)的时间开销.
loc100分支是本文中使用的最简实现, 没有任何外部依赖, main分支中的实现面向生产环境, 要快4倍左右.
如果要生产环境使用, 移步slim .
用20万个网上词汇来测试本文实现的succinctSet:
- succinctSet 空间开销是源数据的57% .
- Has()开销为350 ns.
原始数据大小: 2204 KB
跟 string 数组的 bsearch, 以及google-btree的对比:
Data | Engine | Size(KB) | Size/original | ns/op |
---|---|---|---|---|
200kweb2 | bsearch | 5890 | 267% | 229 |
200kweb2 | succinct.Set | 1258 | 57% | 356 |
200kweb2 | btree | 12191 | 553% | 483 |
场景和问题
计算机中的信息, 为了查询方便, 几乎都是排序存储的(即使是hash结构, hash map 中的 hash 值也是顺序存储的).
数据存储领域, 大部分数据也都是静态的, 例如数据库底层的一个page, rocksdb的一个sstable. 数据越来越大后对存储空间的开销也越来越敏感, 毕竟影响性能的主要瓶颈都在IO上, 不论是CPU对主存的访问延迟, 还是内存到磁盘的延迟, 每2层之间的IO延迟, 基本都在1~2个量级左右. 于是更小的存储开销, 不仅节省存储成本, 另一个bonus是几乎毫无疑问的会提升性能,
本文针对这一个广泛使用的场景: 静态排序数据, 提供一个通用的实现方法来压缩空间开销.
生产环境中使用的算法, 和本文介绍的方法同源, 但包括更多的优化, 例如通过SIMD指令一次处理多个字节的比较, 用bitmap来优化labels的存储, 对只有一个出向label的节点的合并优化等.
思路: 前缀树
前缀树, 或字典树, prefix tree, trie, 是解决这类问题的一个典型思路. 例如要存储5个key: [ab, abc, abcd, axy, buv] 可以建立下面这样一个前缀树, 省去大量重复的前缀, 其中^是root节点(也记做0), 1, 2, 3…是trie节点,$标记一个叶子节点, 字母a, b...表示一个节点到下级节点的边(labeled branch):
^ -a-> 1 -b-> 3 $ | | `c-> 6 $ | | `d-> 9 $ | `x-> 4 -y-> 7 $ `b-> 2 -u-> 5 -v-> 8 $
但是! 在 trie 的实现中, 就像一般的树形结构实现一样, 需要大量的指针, 每个 label 到其指向的节点需要占用一个指针. 在64位系统中一个指针就要占8字节, 整个 trie 中指针数量至少也是叶子节点的数量.
如果要存储的字符串长度比较短, 很可能编码成 trie 之后, 因为指针开销, 要占用更大空间. 即使是存储较长的字符串, 大部分场合指针的开销也无法忽略不计.
于是对于这类key集合确定的场景(例如rocksdb中的sstable, 就是典型的静态排序key的存储), 使用压缩的前缀树是一种更简洁有效的方式来去掉指针开销.
前缀树的压缩算法
在这个前缀树中, 每个节点至多有256个出向label, 指向下一级节点. 一个节点可以是inner节点, 例如root节点^, 或1, 2, 3. 也可以是叶子节点, 例如3, 6, 9. 这里3既是一个inner节点也是一个leaf节点.
^ -a-> 1 -b-> 3 $ | | `c-> 6 $ | | `d-> 9 $ | `x-> 4 -y-> 7 $ `b-> 2 -u-> 5 -v-> 8 $
要压缩这个 trie, 对每个 trie 节点, 我们需要的最核心的信息是:
- 一个节点的分支(label)都有哪些,
- 以及label指向的节点的位置.
我们有以下这种紧凑的结构来描述这个 trie:
一个 trie 节点的出向 label 都存储在一个[]byte中, 再用一个 bitmap 来描述每个节点的分支, 后面通过这个 bitmap 来定位 label 对应的节点.
先把每个节点对应的 label 列出来, 并为每个 label 分配一个bit0来标记:
^: {a, b} 00 1: {b, x} 00 2: {u} 0 3: {c} 0 4: {y} 0 5: {v} 0 6: {d} 0 7: ø 8: ø 9: ø
然后将所有的label保存在一个[]byte中, 再将对应的标记label的多个0...用1做分隔符连接到一起: 这2块信息是 succinctSet 核心的2个字段, 有了这2部分数据就可以实现(不算高效的)key查找:
labels(ignore space): ab bx u c y v d øøø label bitmap: 0010010101010101111 node-id: 0 1 2 3 4 5 6 789 // node-id 不需要存储
压缩后的查询
在标准的 trie 中查找一个 key 很简单, 在第L层的一个节点上, 查找key[L]的byte是否是 trie 节点的一个出向 label, 如果是, 走到下一个节点, 否则终止.
例如对axy的查找, 要经历3次查找,^ -a-> ① -x-> ④ -y-> ⑦ $:
^ -a-> ① -b-> 3 $ | | `c-> 6 $ | | `d-> 9 $ | `x-> ④ -y-> ⑦ $ `b-> 2 -u-> 5 -v-> 8 $
在 succinctSet 中的查找也是一样, 唯一不同的是如何在这个没有指针的结构中找到某个出向 label 对应的子节点.
我们把 trie 原来的 label 到子节点的关系, 在压缩后的结构中画出来, 端详端详:
| .-----. | .--. | .---|-. | |.-|--. | | .-|-|. | || ↓ ↓ | | | ↓ ↓↓ | labels(ignore space): ab bx u c y v d øøø | label bitmap: 0010010101010101111 | node-id: 0 1 2 3 4 5 6 789 | || | ↑ ↑ ↑ | ↑ | || `-|-|-' `---' | |`---|-' | `----'
从上图可以看出,
除了根节点^, 每个节点都有一个0与之对应(节点入向 label 对应位置的0). 图中上下箭头, 是 label 到节点的关系, 也就是每个0跟它指向的子节点的对应关系.
每个节点也都有一个1与之一一对应, 也就是每个节点都有一个结束标记1.
例如:
bitmap 中 第0个0对应节点1:bx, 第1个0对应节点2:u…
同理节点与1的关系也类似, 第0个1对应root节点^,0:ab, 第1个1对应节点1:bx, 第2个1对应节点2:u…
你品, 你细品…
品完后发现,要找到某个 label 指向的节点, 只需要先数数这个 label 对应第几个0, 例如是第i个0, 再找到bitmap中的第i个1, 第i个1后面就是 label 对应的节点位置了 .
这就是在压缩前缀树中逐层定位节点的算法.
举个栗子
我要给这篇文章打分:
评价列表(1)
+1 guest voted at 2022-03-15 17:40:03