Succinct Trie - 基于 LOUDS 编码的压缩字典树

最近在学习 ElasticSearch 的 FST 结构发现,虽然它压缩了前后缀可以让占用空间极大缩小,但依然有对象头和指针的开销,如果能把这部分开销去掉,压缩率还能再上一层楼。于是经过调研发现一种叫“简洁数据结构”(Succinct Data Structure)的东西,它在占用极小空间下还能提供高效查询操作。对此比较好奇它的实现原理,遂深入探索,想用 Java 实现一个比 FST 占用更小的 Trie 结构,于是就有了这篇文章。

p.s. 部分参考图和代码源自《基于 LOUDS 的 Succinct Set 详解

Git 提交规范

经常看到别人提交的代码记录里面包含一些feat、fix、chore等等,而我在提交时也不会区分什么,直接写下提交信息,今天就来看一下怎么个事,就拿 element-plus 举例来看一下