重新认识数据结构：从空间占用开始

数据结构与算法是基础知识了，一般涉及数据结构的增删改查，深入一点的可以估计增删改查的时间复杂度和空间复杂度。本文介绍另一种衡量数据结构的方式：空间占用。这种分类让我对数据结构有了一个全新的认识。

假如需要存储数据的信息论（香农之子）最低空间占用为Z个bit（其实就是原始数据的空间占用），那么对这些数据的一种表示（数据结构）可以根据其空间占用分成三类：空间占用逐渐增大。

（1）Implicit（隐式）：占用 Z+O(1) bits，如 Z+3 bits

（2）Succinct（简洁）：占用 Z+o(Z) bits，如 Z + lgZ bits

（3）Compact（紧凑）：占用 O(Z) bits，如 2Z bits，1.1Z bits

这里可能会造成疑惑，Succinct 和 Compact 有啥区别，个人认为附加的空间只要和 Z 不是线性关系就是 Succinct，是线性关系就是 Compact。

空间占用 Implicit < Succinct < Compact。看一个比较形象的图：空间占用就是这些数据的围墙，实际建筑物占空间并不大，重点是围墙内的面积。这张图就很 Succinct 了。

下边通过例子来具体介绍：

Implicit 数据结构

普通数组：除了原始数据，只多存了一个数组长度。（和链表区分开，链表还有数据之间的指针）

以null结尾的字符串：除了原始字符数据，只多了一个 null 字符。

这些数据结构基本都是一些非常简单的数据结构，虽然空间占用很高效，但是如果不做特殊处理，在其上的操作复杂度都不低，查找都是O(n)的。当然也可以先将数据排序再存到数组里，也属于 implicit 数据结构。

为什么叫 implicit 呢，我觉得应该是原始数据中隐藏着结构，因为并没有用指针之类的明显表示数据之间的关系。

Succinct 数据结构

这种数据结构的定义是 Jacobson 1989 年左右提出来的。

链表就不是 Succinct 数据结构，在链表中每个数据都带一个指针，假如数据有 n 个，为了区分这n个数据，指针的长度最少为 lg(n)个 bit。比如要区分 4 个数据至少需要 2 个bits。这样假如每个数据占 x 个bit，Z=xn，指针占用 nlg(n)个，总占用 ( 1+x/lg(n) ) Z 个bits。Z 的一次项系数大于1。

Succinct的起源是用 Level-Ordered Unary Degree Sequence（LOUDS）编码将一棵普通的树形结构编码成 Succinct tree。

看下面这棵树（来自《Space-efficient Static Trees and Graphs》），其每个节点的编码是这样来的：如果其有 n 个子节点，那么他的编码就是 n 个 1 加一个 0。

接下来用一另一棵树介绍这些节点编码如何组织成一个数组：（为什么换个图呢，因为不是我画的，来自《SuRF: Practical Range ery Filtering with Fast Succinct Tries》）。我们回过头来看 LOUDS 的名字，他是分层的，有序的。这些编码按层次从左到右依次排列，组成了 LOUDS 编码，如下图：

这样，就将一棵树编码成了一个数组。省掉了指针，但是这样怎么查找子节点或父节点呢？

在这个数组上提出了两个基本操作：

看不下去后边的等号公式可以不看，直接听我讲：

rank_q(x) 返回数组位置 x 之前（包括x）值为 q 的数据个数。比如位置 5 之前有几个 1 为 rank_1(5)。

select_q(x) 返回第 x 个 q 的数据位置。比如第 5 个 1 的位置为 select_1(5)。

那么，这两个操作如何实现节点的查找呢？首先一个节点是有多个 bit 编码的，由 0 分割。一般一个节点用它的起始位置 p 表示。节点的下标从 0 开始。

（1）第 i 个节点的位置：select_0(i)+1，即第 i 个0的位置 +1。

（2）起始位置为 p 的节点的 下标为 k 的子节点的位置：select_0(rank_1(p+k)) +1

（3）起始位置为 p 的节点的父亲节点的位置：select_1(rank_0(p))

看，他们搭配出来可以在数组里完成树的功能，这就是索引之美。

Compact 数据结构

我们常用的数据结构实现方式大部分都是 Compact 数据结构。需要用指针来记录数据的相对位置和关系。

如链表，用指针实现的树。

总结

树、堆等只是逻辑数据结构，是实现方式决定了其是 Succinct 还是 compact。而这个实现方式的区分一般就看他是用数组实现的还是用指针实现的，比如，树状数组就属于 Succinct，用链表实现的二叉树就是Compact。Implicit 数据结构基本都是基础数据结构，很难玩出花样，而Succinct 数据结构未来可能会有更多应用。

参考：

https://en.wikipedia.org/wiki/Succinct_data_structure

《SuRF: Practical Range ery Filtering with Fast Succinct Tries》

《Space-efficient Static Trees and Graphs》