arrays - 排序数组的紧凑数据结构

Question

我有一个表格，其中包含排序后的数字，例如:

1 320102
2 5200100
3 92010023
4 112010202
5 332020201
6 332020411
: 
5000000000 3833240522044511
5000000001 3833240522089999
5000000002 4000000000213312

给定记录数，我需要 O(log n) 时间内的值。记录号为64位长，并且不存在缺失的记录号。这些值是 64 位长，已排序且 value(n) < value(n+1)。

显而易见的解决方案是简单地创建一个数组并使用记录数作为索引。这将花费每个值 64 位。

但我想要一种更节省空间的方式来做到这一点。因为我们知道值总是在增加，所以这应该是可行的，但我不记得可以让我这样做的数据结构。

一个解决方案是在数组上使用 deflate，但这不会给我访问元素的 O(log n) - 因此是 Not Acceptable 。

你知道一种数据结构可以给我:

• O(log n) 访问
• 空间要求 < 64 位/值

= 编辑=

由于我们提前知道所有数字，因此我们可以找到每个数字之间的差异。通过取这些差异的第 99 个百分位数，我们将得到一个相对适中的数字。取 log2 将为我们提供表示适度数字所需的位数 - 让我们称之为适度位数。

然后创建这个:

64-bit value of record 0
64-bit value of record 1024
64-bit value of record 2048
64-bit value of record 3072
64-bit value of record 4096

然后是所有记录的增量表:

modest-bits difference to record 0
modest-bits difference to previous record
1022 * modest-bits difference to previous record
modest-bits difference to record 1024

记录 k*1024 的适度位差将始终为 0，因此我们可以将其用于信令。如果它非零，那么接下来的 64 位将是一个指向简单数组的指针，该数组将接下来的 1024 条记录作为 64 位值。

由于选择的适度值是第 99 个百分位数，因此最多会发生 1% 的时间，因此最多浪费 1% * n * 适度位 + 1% * n * 64 位 * 1024。

空间:O(适度位 * n + 64 位 * n/1024 + 1% * n * 适度位 + 1% * n * 64 位 * 1024)

查找:O(1 + 1024)

(99%和1024可能需要调整)

= 编辑2 =

基于上述想法，但浪费的空间更少。创建这个:

64-bit value of record 0
64-bit value of record 1024
64-bit value of record 2048
64-bit value of record 3072
64-bit value of record 4096

对于所有无法用适度位表示的值，将大值表创建为树:

64-bit position, 64-bit value
64-bit position, 64-bit value
64-bit position, 64-bit value

然后是所有记录的增量表，每 1024 条记录重置一次:

modest-bits difference to record 0
modest-bits difference to previous record
1022 * modest-bits difference to previous record
modest-bits difference to record 1024

而且还会重置大值表中的每个值。

空间:O(适度位 * n + 64 位 * n/1024 + 1% * n * 2 * 64 位)。

查找需要搜索大值表，然后查找第 1024 个值，最后对适度位值求和。

查找:O(log(大值表) + 1 + 1024) = O(log n)

你能改进这个吗？或者以不同的方式做得更好？

Answer 1

OP建议将数字分成 block (仅一次)。但这个过程可能会继续下去。再次分割每个 block 。再说一次......最后我们可能会得到一个二进制特里树。

根节点包含索引最少的数字的值。它的右后代存储表中中间数字与索引最少的数字之间的差值:d = A[N/2] - A[0] - N/2。对于其他右后代(图中的红色节点)继续进行此操作。叶节点包含前面数字的增量:d = A[i+1] - A[i] - 1。

因此，存储在 trie 中的大多数值都是增量值。它们每个占用的空间都小于 64 位。为了紧凑性，它们可以作为可变位长数字存储在比特流中。为了获取每个数字的长度并在 O(log N) 时间内在该结构中导航，比特流还应该包含(一些)数字和(一些)子树的长度:

1. 每个节点包含其左子树(如果有)的长度(以位为单位)。
2. 每个右后代(图中的红色节点)(叶节点除外)都包含其值的长度(以位为单位)。叶节点的长度可以根据从根到该节点的路径上的其他长度来计算。
3. 每个右后代(图中的红色节点)都包含对应值与路径上最近的“红色”节点的值的差异。
4. 所有节点都打包在比特流中，从根节点开始，按顺序排列:左后代始终跟随其祖先；右后代跟随子树，以左后代为根。

要访问给定索引的元素，请使用索引的二进制表示形式来遵循 trie 中的路径。遍历此路径时，将“红色”节点的所有值加在一起。当索引中不再有非零位时停止。

有多种选项可以存储 N/2 值长度:

1. 根据需要为每个长度分配尽可能多的位，以表示从最大长度到低于平均长度的所有值(不包括一些非常短的异常值)。
2. 还排除一些长异常值(将它们保留在单独的 map 中)。
3. 由于长度可能分布不均匀，因此对值长度使用霍夫曼编码是合理的。

固定长度或霍夫曼编码对于每个特里树深度都应该不同。

N/4 子树长度实际上是值长度，因为 N/4 最小子树包含单个值。

其他 N/4 子树长度可以存储在固定(预定义)长度的字中，因此对于大型子树，我们仅知道近似(向上舍入)长度。

对于 2³⁰ 个全范围 64 位数字，我们必须打包大约 34 位值，对于 3/4 节点，大约需要打包 34 位值。 4 位值长度，每四个节点有 10 位子树长度。节省 34% 的空间。

---

示例值:

0 320102
1 5200100
2 92010023
3 112010202
4 332020201
5 332020411
6 3833240522044511
7 3833240522089999
8 4000000000213312

尝试这些值:

root               d=320102           vl=19    tl=84+8+105+4+5=206
   +-l                                         tl=75+4+5=84
   | +-l                                       tl=23
   | | +-l
   | | | +-r       d=4879997          (vl=23)
   | | +-r         d=91689919         vl=27
   | |   +-r       d=20000178         (vl=25)
   | +-r           d=331700095        vl=29    tl=8
   |   +-l
   |   | +-r       d=209              (vl=8)
   |   +-r         d=3833240190024308 vl=52
   |     +-r       d=45487            (vl=16)
   +-r             d=3999999999893202 vl=52

值长度编码:

           bits start end
Root       0    19    19
depth 1    0    52    52
depth 2    0    29    29
depth 3    5    27    52
depth 4    4    8     23

每个子树长度需要 8 位。

这是编码流(为了便于阅读，二进制值仍以十进制显示):

bits value                      comment
19   320102                     root value
8    206                        left subtree length of the root
8    84                         left subtree length
4    15                         smallest left subtree length (with base value 8)
23   4879997                    value for index 1
5    0                          value length for index 2 (with base value 27)
27   91689919                   value for index 2
25   20000178                   value for index 3
29   331700095                  value for index 4
4    0                          smallest left subtree length (with base value 8)
8    209                        value for index 5
5    25                         value length for index 6 (with base value 27)
52   3833240190024308           value for index 6
16   45487                      value for index 7
52   3999999999893202           value for index 8

总共 285 位或 5 个 64 位字。我们还需要存储值长度编码表(350 位)中的位/起始值。为了存储 635 位，我们需要 10 个 64 位字，这意味着这么小的数字表无法压缩。对于较大的数字表，值长度编码表的大小可以忽略不计。

要搜索索引 7 的值，请读取根值 (320102)，跳过 206 位，添加索引 4 的值 (331700095)，跳过 8 位，添加索引 6 的值 (3833240190024308)，添加索引 7 的值 ( 45487)，并添加索引(7)。结果是 3 833 240 522 089 999，符合预期。