1
+1 100行代码的压缩前缀树: 50% smaller
这文介绍一个压缩前缀树实现的sorted set(github: succinct.Set), 区区95行代码, 包含了一组完整的功能:
用 前缀树 存储一个排序数组, 去掉指针, 压缩掉50%的空间;
例如在本文的例子中, 存储2.4MB的200万个单词, 只需要1.2MB.
创建: 从key列表创建一个压缩的前缀树;
查询: 支持Has() 操作来查询1个key是否存在;
优化: 通过索引来加速 bitmap 的操作, 将较大的 bitmap 操作优化到O(1)的
查看全文: http://www.udpwork.com/item/17474.html
用 前缀树 存储一个排序数组, 去掉指针, 压缩掉50%的空间;
例如在本文的例子中, 存储2.4MB的200万个单词, 只需要1.2MB.
创建: 从key列表创建一个压缩的前缀树;
查询: 支持Has() 操作来查询1个key是否存在;
优化: 通过索引来加速 bitmap 的操作, 将较大的 bitmap 操作优化到O(1)的
查看全文: http://www.udpwork.com/item/17474.html