10

我有特殊需要,最重要的问题是:

  • 在记忆中
  • 非常低的内存占用
  • 速度

这是我的“问题”:我需要在内存中存储大量非常稀疏的位数组。这些位集是“仅附加”的,主要用于交叉路口。巨大的,我的意思是高达 200 000 位数组。

每个位集的范围应在 [0...16 000 000] 之间。

我使用“仅”包含一些实际数据的 10 673 位数组进行了一些预测试,得到了以下结果:

  1% of the bit arrays (  106 bit arrays) Hamming weight: at most     1 bit  set
  5% of the bit arrays (  534 bit arrays) Hamming weight: at most     4 bits set
 10% of the bit arrays ( 1068 bit arrays) Hamming weight: at most     8 bits set
 15% of the bit arrays ( 1603 bit arrays) Hamming weight: at most    12 bits set
 20% of the bit arrays ( 2137 bit arrays) Hamming weight: at most    17 bits set
 25% of the bit arrays ( 2671 bit arrays) Hamming weight: at most    22 bits set
 30% of the bit arrays ( 3206 bit arrays) Hamming weight: at most    28 bits set
 35% of the bit arrays ( 3740 bit arrays) Hamming weight: at most    35 bits set
 40% of the bit arrays ( 4274 bit arrays) Hamming weight: at most    44 bits set
 45% of the bit arrays ( 4809 bit arrays) Hamming weight: at most    55 bits set
 50% of the bit arrays ( 5343 bit arrays) Hamming weight: at most    67 bits set
 55% of the bit arrays ( 5877 bit arrays) Hamming weight: at most    83 bits set
 60% of the bit arrays ( 6412 bit arrays) Hamming weight: at most   103 bits set
 65% of the bit arrays ( 6946 bit arrays) Hamming weight: at most   128 bits set
 70% of the bit arrays ( 7480 bit arrays) Hamming weight: at most   161 bits set
 75% of the bit arrays ( 8015 bit arrays) Hamming weight: at most   206 bits set
 80% of the bit arrays ( 8549 bit arrays) Hamming weight: at most   275 bits set
 85% of the bit arrays ( 9083 bit arrays) Hamming weight: at most   395 bits set
 90% of the bit arrays ( 9618 bit arrays) Hamming weight: at most   640 bits set
 95% of the bit arrays (10152 bit arrays) Hamming weight: at most  1453 bits set
 96% of the bit arrays (10259 bit arrays) Hamming weight: at most  1843 bits set
 97% of the bit arrays (10366 bit arrays) Hamming weight: at most  2601 bits set
 98% of the bit arrays (10473 bit arrays) Hamming weight: at most  3544 bits set
 99% of the bit arrays (10580 bit arrays) Hamming weight: at most  4992 bits set
100% of the bit arrays (10687 bit arrays) Hamming weight: at most 53153 bits set

看到所涉及的数字,我显然需要使用压缩位数组,这不是问题:看到位数组是“仅附加”的,它应该很容易处理。

打开的位数组位有点分组,但不完全。所以你会倾向于在同一个区域有几个位(但通常不是一个接一个,这使得 RLE 不太适合那些打开的位)。

我的问题是使用什么样的压缩?

现在我不知道我应该把我的第一种方法放在这里还是回答我自己的问题。

基本上我想象了一个使用非常愚蠢的编码的“最坏情况”场景:

  • 1 位:如果打开,接下来的 5 位确定需要多少位来计算“跳过”,如果关闭,则优化:接下来的 5 位确定需要多少位(即 'on' 或 'off ',不跳过)[只有在确定比其他表示更有效时才会切换到,所以当它启动时,它应该始终是优化(大小方面)]

  • 5 位:在下一位之前我们可以跳过多少位

  • x位:跳过

这是一个示例:一个位数组有 3 个位集,第一个位在 3 098 137,第二个在 3 098 141,第三个在 3 098 143。

                               +-- now we won't skip
                               |
                               |     +-- 3 because we need 3 bits to store "6" (from 3 098 138 to 3 098 143)
                               |     |    +--- 3 098 141 is on
  22    3 098 137              |     3    | +- 3 098 143 is on
1 10110 1011110100011000011001 0 00011 000101 etc. 

第一个位告诉我们要跳过位。5 下一位(总是 5)告诉我们需要多少位,告诉我们将跳过多少位 22 位告诉跳到 3 098 137 一位告诉现在我们没有跳过位 5 下一位(总是 5)告诉我们将“按原样”读取多少位 6 位:关闭、关闭、关闭、开启、关闭、开启意味着 3 098 141 和 3 098 143 开启等。

看到这些位数组惊人的稀疏性,这似乎非常节省大小。

所以使用这种编码,我获取了我的样本数据并计算了一个“最坏情况”的场景(我还没有编写算法,我宁愿先从这里输入一些):基本上我认为不仅“大小优化”永远不会启动,而且 5 位将始终设置为其最大值(24 位),这当然不会发生。

我这样做只是为了对“最坏中的最坏”情况有一个非常粗略的近似。

我非常惊喜:

Worst case scenario: 

108 913 290 bits needed for the 10 687 very sparse bit arrays
12.9 MB (13 295 KB)

数据是实际数据并且所有数据都相似,我知道,如果情况变得更糟,我可以将我的 200 000 位数组存储在大约 240 MB 中,这很好。

我很确定实际的编码会比这少,但由于我还没有真正编写它,我只能(非常容易地)计算“最坏情况”,这就是为什么我只显示那个。

关于如何提高尺寸效率的任何提示/想法(记住这些是超稀疏位数组,应该有数十万个,它们必须在内存中,并且它们应该“仅附加”) ?

关于我的“仅附加”案例

基本上我有一个不断增长的“扩展”(范围,但“扩展”是我理解的实际术语)和许多具有一些位集的位数组。当范围从 0 到 1 000 000 时,所有位数组都从 0 到 1 000 000 到。当范围增长到 1 000 001 时,所有位数组也在增长,全部增长一位。但是大多数这些位数组的末尾会附加一个“0”,而大约 4 到 8 个位数组的末尾会附加一个“1”。但是,我无法提前预测哪些位数组将附加 0 或 1。

所以我有很多大小相同的位数组,它们都非常稀疏(< 0.5% 的位集)并且随着范围的增长而“增长”(所以它们总是在增长以同样的速度)。


Judy 数组很棒。但几年前我读到了它们,这些东西“在我头上”。Judy 数组是一个仅限 C 语言的 20KLOC 库,我绝对不会重新实现它。但他们太棒了。

所以我想我需要补充一下,我希望所有这些都保持相对简单,这并不是牵强附会,因为我非常稀疏的位数组的特殊“仅附加”属性。

4

6 回答 6

4

你没有说你想使用什么编程语言。听起来您不想要 Judy,因为它是“仅限 C”...如果您使用的是 C#,那么您可以改用我的Compact Patricia Trie。Is 几乎是 4500 LOC(已注释)并且使用与 Judy 类似的想法,但由于 .NET 的限制,每个 trie 的大小和速度并不理想。它也没有针对计算交叉点进行优化,但可以添加这样的算法。关于 CP Tries 的文章没有强调这一点,但它可以比字典更紧凑地存储集合(稀疏位数组)(文章中的图表显示的是字典的大小和速度,而不是集合)。

最好的情况是密集的比特簇。对于 50% 的占用率(每隔一个位设置),每个密钥需要少于 8 位(每个整数少于 4 位)。(更正:少于 8 位,不多于。)

如果您只需要数据的近似表示,请使用布隆过滤器

顺便说一句,“仅附加”是什么意思?是说你只加了key,还是说你加的每一个key都比你之前加的key大?

更新:由于您只添加更大的密钥,您可能应该为您的情况设计一个特殊的算法。IMO,在设计自定义算法时,应使其尽可能简单。所以这是我的想法,它假设不同位集的密钥是不相关的(因此尝试在不同位集之间压缩数据没有好处):

位集由 32 位插槽的排序数组表示。因为它是排序的,所以您可以使用二进制搜索来查找键。每个槽由一个 24 位的“前缀”和 8 位的“标志”组成。每个插槽代表一个包含 8 个键的区域。“标志”告诉您该区域中的 8 个密钥中的哪一个存在于位集中,“前缀”通过指定密钥的位 3 到 26 告诉您我们正在谈论的区域。例如,如果位集中的以下位为“1”:

1, 3, 4, 1094, 8001, 8002, 8007, 8009

...然后位集由 4 个插槽(16 个字节)的数组表示:

Prefix:     0,  136, 1000, 1001
 Flags:  0x15, 0x40, 0x86, 0x02

第一个槽代表1、3、4(注意1、3、4位设置在数字0x15中);第二个槽代表 1094 (136 * 8 + 6);第三个插槽代表 8001、8002 和 8007;第四个槽代表8009。这有意义吗?

我不知道这是否像您的想法一样紧凑。但我认为你会得到更快的查询和更快的修改,而且实现起来也相当容易。

于 2010-11-02T16:18:47.353 回答
3

您可以查看压缩位图。一种常见的策略是使用字对齐的游程长度编码。

C++ 实现:

https://github.com/lemire/EWAHBoolArray

Java实现:

https://github.com/lemire/javaewah

参考:

Daniel Lemire、Owen Kaser、Kamel Aouiche,Sorting 改进了字对齐位图索引。数据与知识工程 69 (1),第 3-28 页,2010 年 。http://arxiv.org/abs/0901.3751

于 2010-11-04T12:44:49.010 回答
3

您可以将二叉树用于位数组。比如说,你有一个范围为 [M..N] 的数组。以这样的方式存储它:

为 [0...ram size] 选择一些数字编码,例如 Fibonacci、Golomb 或 Rice 代码(您可以在使用实际数据分析您的程序后选择最合适的表示)。

  1. 如果数组为空(未设置位),则将其存储为数字 0。
  2. 如果数组已满(设置所有位),则将其存储为数字 1。
  3. 否则将其分为两部分:[M..(M+N)/2-1] 中的 A 和 [(M+N)/2..N] 中的 B
  4. 使用此算法递归生成 P0 和 P1 的表示。
  5. 获取 P0 的长度(以位或其他单位为单位,长度可能是整数)并将其存储为数字(如果长度可能为 1,则可能需要加 1,例如,将 0 存储为单个位 0)。
  6. 存储 P0 然后 P1。

在这种情况下,如果限制是常见的,则交集和并集的操作是微不足道的递归:

路口:

  1. 如果数组 A 为空,则存储 0。
  2. 如果数组 A 已满,则存储 B 的副本
  3. 否则拆分数组,使两半相交,存储前半部分的长度,然后存储两半。

该算法可以处理位(如果您需要它们最紧凑)和字节/字(如果位操作如此缓慢)。

您也可以为具有单个位集的数组添加特殊编码,所有数组的大小都小于某个限制(例如 8 个元素)以降低递归级别。

缺点是,如果没有一些技巧,在数组中添加/删除元素是复杂的操作(与交集/联合操作一样复杂)。

例如,设置了单个 0xAB 位的数组应存储在 0..0xFF 数组中,如下所示(伪代码):

0  1      2   3  4      5  6  7      8  9  10     11 12     13    14     15     16
1, EMPTY, 13, 1, EMPTY, 9, 1, EMPTY, 5, 1, EMPTY, 1, EMPTY, FULL, EMPTY, EMPTY, EMPTY
                                                   |  AA  | AB  |
                                         |A8..A9| AA    ..   AB |
                                      | A8         ..        AB |AC..AF|
                            |A0..A7| A8             ..              AF |
                         | A0                 ..                    AF |B0..BF|
               |80..9F| A0                        ..                       BF |
            | 80                                 ..                        BF |C0..FF|
 | 0..7F| 80                                          ..                          FF |       

EMPTY 和 FULL 是空数组和完整数组的代码,数字是元素的长度(应该替换为以字节、位为单位的实际长度)

如果您不需要快速的单个位检查,您可以使用最简单的方法:只需使用代码存储设置位之间的距离:fibonacci、rice、golomb、levenshtein、elias 等,或者发明另一种。请注意,为了获得最小的代码长度,您应该使用代码长度尽可能接近 -log p/log 2 的代码,其中 p 是该代码的概率。您可以为此使用霍夫曼代码。

例如,使用 elias gamma 代码,所以数组是这样的:

0 1 0000 1 1 000 1 0 1 000000000000000000 1 000000000000000000 
2     5   1   4    2         19                   18           (distance)

应编码为:

010 00101 1 00100 010 000010011 000010010
 2    5   1   4    2     19        18     (distance code explained)

对于具有均匀位分布的数组来说,最紧凑的是算术编码,但它非常消耗 CPU 时间。因为您必须一点一点地读取和写入这样的数组,而没有可用的快速跳过。

于 2010-11-02T15:35:20.300 回答
2

即使它们不是您正在寻找的东西,也值得一试Judy trees。Judy 是一个针对有序地图进行了高度优化的库,其中一种配置专门设计为位集而不是地图。我不认为交集是原生优化的操作之一,虽然......

总体思路是使用每层具有固定地址位数的树,并利用每一层的稀疏性。即使在最坏的情况下,这也会产生非常好的压缩效果,并且查询性能也很快。我相信交叉口操作会相对简单并且可能非常快。

无论如何,从最好的人那里偷东西总是一个好主意!

于 2010-11-01T23:52:25.977 回答
1

您可能对二元决策图 (BDD),更准确地说是零抑制二元决策图 (ZBDD) 感兴趣。

它们用于以压缩方式表示集合。与其他压缩表单不同,操作(例如设置交叉点或元素插入 - 您的“仅附加”的东西?)直接在压缩表单上工作。

于 2010-11-02T16:58:47.903 回答
1

考虑到无论如何您都要做一堆交集测试,也许您应该尝试并行存储所有位向量。一个稀疏的 16M 条目列表。该列表中的每个条目都包含一个列表,其中列出了 200k 个输入位向量中的哪些在该位置具有“1”。看起来您希望每个输入向量只设置大约 5 位,或者总共 1M 条目?为顶层和桶采用稻草人链表实现,最坏的情况是根本没有交集(因此 1M 桶,每个桶有 1 个元素),您可以将其全部存储在 32MB 中。

于 2010-11-02T00:19:34.110 回答