Syn*_*r0r 10 compression algorithm bitarray in-memory
我有一个特殊的需求,最重要的问题是:
这是我的"问题":我需要在内存中存储大量非常稀疏的位数组.这些位集仅"附加",主要用于交叉点.通过巨大的,我的意思是高达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位确定字面上也要采用多少位(即'开'或'关' ',没有跳过)[这只会在确定比其他表示更有效时切换到,所以当它开始时,它应该始终是一个优化(大小)]
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数组是一个只有C的20KLOC库,我绝对不会重新实现它.但他们太棒了.
所以我想我需要添加我喜欢所有这些以保持相对简单,这不是一个牵强附会看到我的稀疏位数组的特殊"仅附加"属性.
即使它们不完全是您正在寻找的东西，也值得查看Judy trees。Judy 是一个针对有序映射进行深度优化的库，其中一种配置是专门设计为位集而不是映射的。不过，我不认为交集是本机优化的操作之一......
总体思路是使用每层具有固定数量地址位的树，并利用每层的稀疏性。即使在最坏的情况下，这也会产生相当好的压缩，并且查询性能也很快。我相信交叉操作会相对简单并且可能非常快。
无论如何，从最好的那里窃取总是一个好主意！