2

我有一个带有排序数字的表格，例如：

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) 来访问一个元素 - 因此是不可接受的。

你知道一个可以给我的数据结构：

  • 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(modest-bits * n + 64-bit * n / 1024 + 1% * n * 2 * 64-bit)。

查找需要搜索大值表，然后查找第 1024 个值，最后将适度位值相加。

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

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

4

3 回答 3

2

OP 建议将数字分成块（仅一次）。但这个过程可能会继续下去。再次拆分每个块。再一次……最后我们可能会得到一个二叉树。

在此处输入图像描述

根节点包含索引最小的数字的值。它的右后代存储表中的中间数字与索引最小的数字之间的差异：d = A[N/2] - A[0] - N/2。这对其他右后裔（图中的红色节点）继续进行。叶节点包含来自前面数字的增量：d = A[i+1] - A[i] - 1.

因此，存储在 trie 中的大多数值都是 delta 值。它们中的每一个都占用不到 64 位。为了简洁起见，它们可以作为可变位长数字存储在位流中。要获取每个数字的长度并在 O(log N) 时间内在此结构中导航，比特流还应该包含（一些）数字和（一些）子树的长度：

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

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

有几种存储 N/2 值长度的选项：

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

对于每个 trie 深度，固定长度或 Huffman 编码都应该不同。

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

其他 N/4 子树长度可以存储在固定（预定义）长度的字中，因此对于大型子树，我们只知道近似（向上取整）长度。

对于 2 30 个全范围 64 位数字，我们必须打包大约 34 位值，对于 3/4 个节点，大约 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。

于 2012-09-14T15:47:05.837 回答
1

正如您在问题中概述的那样，我会分块进行。选择一个块大小k，您可以接受在到达您所追求的值之前必须平均解码k/2值。对于n 个总值，您将有n/k个块。具有n/k个条目的表将指向数据流以查找每个块的起点。对于二进制搜索，查找该表中的位置将是 O(log( n/k ))，或者如果表足够小并且如果它很重要，您可以使用辅助哈希表使其大约为 O(1)。

每个块都以一个 64 位的起始值开始。之后的所有值都将存储为前一个值的增量。我的建议是将这些增量存储为霍夫曼代码，说明下一个值中有多少位，然后是那么多位。霍夫曼代码将针对每个块进行优化，并且该代码的描述将存储在块的开头。

您可以通过在每个值前面加上 6 位来简化这一点，后面的位数在 1..64 范围内，实际上是一个平坦的 Huffman 码。根据位长的直方图，与平面码相比，优化的 Huffman 码可以剔除大量的位。

一旦你完成了这个设置，你就可以对k进行试验，看看你能把它做得多小，并且对压缩的影响仍然有限。

于 2012-09-13T17:23:07.607 回答
0

我不知道这样做的数据结构。

获得空间且不损失太多速度的明显解决方案是根据您存储的不同 int 大小创建具有不同数组大小的自己的结构。

伪代码

class memoryAwareArray {
    array16 = Int16[] //2 bytes
    array32 = Int32[] //4 bytes
    array64 = Int64[] //8 bytes

    max16Index = 0;
    max32Index = 0;

    addObjectAtIndex(index, value) {
      if (value < 65535) {
        array16[max16Index] = value;
        max16Index++;
        return;
      }
      if (value < 2147483647) {
        array32[max32Index] = value;
        max32Index++;
        return;
      }

      array64[max64Index] = value;
      max64Index++;
    }

    getObject(index) {
      if (index < max16Index) return(array16[index]);
      if (index < max32Index) return(array32[index-max16Index]);
      return(array64[index-max16Index-max32Index]);
    }
}

沿着这些线的东西不应该改变太多的速度，如果你填满整个结构，你会节省大约 7 千兆。当然，您不会节省太多，因为您的价值观之间存在差距。

于 2012-09-13T14:46:36.503 回答