编码一系列随机可变长度二进制代码的最简洁方法？

Question

假设您有一个,List<List<Boolean>>并且您希望以最紧凑的方式将其编码为二进制形式.

我不关心读写性能.我只是想使用最小的空间.此外,该示例在Java中,但我们不限于Java系统.每个"列表"的长度是无限的.因此,编码每个列表长度的任何解决方案本身必须编码可变长度数据类型.

与此问题相关的是可变长度整数的编码.您可以将每个List<Boolean>视为可变长度unsigned integer.

请仔细阅读问题.我们不仅限于Java系统.

编辑

我不明白为什么很多答案都谈论压缩.我本身并不是在尝试压缩,而只是编码随机的位序列.除了每个比特序列具有不同的长度并且需要保留顺序.

你可以用不同的方式思考这个问题.假设您有一个随机无符号整数列表(无界).如何在二进制文件中编码此列表？

研究

我做了一些阅读,发现我真正想要的是通用代码

结果

我将使用本文中描述的Elias Omega Coding的变体一个新的正整数的递归通用代码

我现在明白,较小整数的表示越小,整数就越大.通过简单地选择具有第一个整数的"大"表示的通用代码,当您需要对任意大整数进行编码时,从长远来看可以节省大量空间.

Answer 1

我正在考虑编码这样的位序列:

head  | value
------+------------------
00001 | 0110100111000011

Head长度可变.它的结束标记为第一次出现1.计算头部中的零数.该value字段的长度将是2 ^ zeroes.由于值的长度是已知的,因此可以重复该编码.由于大小head为log value,随着编码值的大小增加,开销收敛到0%.

附录

如果要更多地调整值的长度,可以添加另一个存储值的确切长度的字段.长度字段的长度可以由头部的长度确定.这是一个9位的例子.

head  | length | value
------+--------+-----------
00001 | 1001   | 011011001

Answer 2

我不太了解Java,所以我想我的解决方案必须是通用的:)

1.压缩列表

由于布尔效率低下,每个都List<Boolean>应该被压缩成一个List<Byte>,这很容易,一次只能抓住它们8个.

最后一个"字节"可能不完整,因此您需要存储已编码的位数.

2.序列化元素列表

您有两种方法可以继续:要么编码列表中的项目数,要么使用模式标记结束.我建议编码项目的数量,模式方法需要转义,这是令人毛骨悚然的,加上打包位更难.

要对长度进行编码,可以使用变量方案:即编码长度所需的字节数应与长度成正比,我已经使用过.您可以通过在第一个字节上使用前缀来指示用于编码长度本身的字节数:

0... .... > this byte encodes the number of items (7 bits of effective)
10.. .... / .... .... > 2 bytes
110. .... / .... .... / .... .... > 3 bytes

它非常节省空间,并且解码发生在整个字节上,因此并不太难.人们可以说它与UTF8方案非常相似:)

3.递归申请

List< List< Boolean > >成为[Length Item ... Item]每个人Item本身就是一个代表的地方List<Boolean>

拉链

我想有一个zlib可用于Java 的库,或者其他类似的deflate或者lcw.将它传递给你的缓冲区并确保精确到希望尽可能多的压缩,无论花费多少时间.

如果你的表示中有任何重复的模式(甚至是你没有看到的模式),它应该能够压缩它.不要愚蠢地相信它并且DO检查"压缩"形式比"未压缩"形式更轻,但情况并非总是如此.

5.例子

一个人注意到跟踪列表的边缘是空间消耗:)

// Tricky here, we indicate how many bits are used, but they are packed into bytes ;)
List<Boolean> list = [false,false,true,true,false,false,true,true]
encode(list) == [0x08, 0x33] // [00001000, 00110011]  (2 bytes)

// Easier: the length actually indicates the number of elements
List<List<Boolean>> super = [list,list]
encode(super) == [0x02, 0x08, 0x33, 0x08, 0x33] // [00000010, ...] (5 bytes)

6.空间消耗

假设我们有一个List<Boolean>的n布尔值,空间消耗编码是:

booleans = ceil( n / 8 )

要编码位数(n),我们需要:

length = 1   for 0    <= n < 2^7   ~ 128
length = 2   for 2^7  <= n < 2^14  ~ 16384
length = 3   for 2^14 <= n < 2^21  ~ 2097152
...
length = ceil( log(n) / 7 )  # for n != 0 ;)

因此要完全编码列表:

bytes =
 if n == 0: 1
 else     : ceil( log(n) / 7 ) + ceil( n / 8 )

7.小名单

但是有一个角落的情况:频谱的低端(即几乎空的列表).

因为n == 1,bytes被评估2,这可能确实看起来很浪费.然而,我不会试图猜测压缩开始后会发生什么.

你可能希望包装更多.如果我们放弃保留整个字节的想法就有可能......

1. 保持长度编码原样(在整个字节上),但不要"填充" List<Boolean>.一个元素列表变为0000 0001 x(9位)
2. 尝试"打包"长度编码

第二点更难,我们实际上是双倍长度编码:

1. 指示编码长度的位数
2. 实际上对这些位的长度进行编码

例如:

0  -> 0 0
1  -> 0 1
2  -> 10 10
3  -> 10 11
4  -> 110 100
5  -> 110 101
8  -> 1110 1000
16 -> 11110 10000 (=> 1 byte and 2 bits)

它适用于非常小的列表,但很快就会退化:

# Original scheme
length = ceil( ( log(n) / 7)

# New scheme
length = 2 * ceil( log(n) )

突破点？ 8

是的,你读得对,它只对少于8个元素的列表更好......而且只有"比特"更好.

n         -> bits spared
[0,1]     ->  6
[2,3]     ->  4
[4,7]     ->  2
[8,15]    ->  0    # Turn point
[16,31]   -> -2
[32,63]   -> -4
[64,127]  -> -6
[128,255] ->  0    # Interesting eh ? That's the whole byte effect!

当然,一旦压缩开始,很可能无关紧要.

我知道你可能会欣赏它recursive的算法,但我仍然建议计算实际空间消耗的数字,甚至更好地实际测试它,并在实际测试集上应用归档.

8.递归/可变编码

我已经阅读了感兴趣TheDon的答案,以及他提交给Elias Omega Coding的链接.

在理论领域,它们是合理的答案.不幸的是,它们非常不实用.主要问题是它们具有非常有趣的渐近行为,但是我们什么时候才需要编码一个技嘉价值的数据呢？很少,如果有的话.

最近一项关于工作中内存使用情况的研究表明,大多数容器都用于十几种(或几十种).只有在极少数情况下我们才能达到千人.当然,对于您的特定问题,最好的方法是实际检查您自己的数据并查看值的分布,但根据经验我会说您不能只关注频谱的高端,因为您的数据位于低端.

TheDon算法的一个例子.说我有一个清单[0,1,0,1,0,1,0,1]

len('01010101') = 8 -> 1000
len('1000')     = 4 -> 100
len('100')      = 3 -> 11
len('11')       = 2 -> 10

encode('01010101') = '10' '0' '11' '0' '100' '0' '1000' '1' '01010101'

len(encode('01010101')) = 2 + 1 + 2 + 1 + 3 + 1 + 4 + 1 + 8 = 23

让我们制作一个小表,使用各种"阈值"来停止递归.它表示各种范围的开销比特数n.

threshold     2    3    4    5      My proposal
-----------------------------------------------
[0,3]    ->   3    4    5    6           8
[4,7]    ->   10   4    5    6           8
[8,15]   ->   15   9    5    6           8
[16,31]  ->   16   10   5    6           8
[32,63]  ->   17   11   12   6           8
[64,127] ->   18   12   13   14          8
[128,255]->   19   13   14   15         16

公平地说,我专注于低端,我的建议适合这项任务.我想强调它不是那么清楚.特别是因为近1,log功能几乎是线性的,因此递归失去了它的魅力.门槛有很大帮助,3似乎是一个很好的候选人......

至于Elias omega coding,情况更糟.来自维基百科的文章:

17 -> '10 100 10001 0'

就是这样,一个大惊小怪的11位.

道德:如果不考虑手头的数据,就无法选择编码方案.

所以,除非你List<Boolean>有数百的长度,不要打扰并坚持我的小提议.

Answer 3

我会使用可变长度整数来编码要读取的位数。MSB 将指示下一个字节是否也是整数的一部分。例如：

11000101 10010110 00100000

实际上意味着：

   10001 01001011 00100000

由于整数连续2次。

这些可变长度整数将告诉有多少位需要读取。并且在开头还有另一个可变长度 int 来告诉有多少位集要读取。

从那时起，假设您不想使用压缩，我认为在大小方面优化它的唯一方法就是根据您的情况进行调整。如果您经常有较大的位集，您可能希望使用短整数而不是字节来进行可变长度整数编码，从而使您在编码本身中浪费更少的位。

编辑我认为不存在一种完美的方法可以一次性实现您想要的一切。你不能凭空创造信息，如果你需要可变长度的整数，显然你也必须对整数长度进行编码。空间和信息之间必然存在权衡，但也存在无法删除以使用更少空间的最少信息。要素以不同速率增长的系统永远无法完美扩展。这就像试图在对数曲线上拟合一条直线。你不能那样做。（此外，这几乎正是您在这里尝试做的事情。）

您无法在整数之外对可变长度整数的长度进行编码并同时获得无限大小的可变整数，因为这需要长度本身是可变长度的，并且无论您选择什么算法，这似乎都是常识对我来说，只使用一个可变长度整数而不是两个或更多整数会更好。

所以这是我的另一个想法：在整数“标头”中，为可变长度整数所需的每个字节写入一个 1。第一个 0 表示“标头”的结束和整数本身的开始。

我试图掌握确切的方程，以确定需要多少位来存储我给出的两种方式的给定整数，但我的对数很生疏，所以我将把它画下来并稍后编辑此消息以包含结果。

编辑 2 以下是方程：

• 解决方案一，每个编码位 7 位（一次一个完整字节）：
  y = 8 * ceil(log(x) / (7 * log(2)))
• 解决方案一，每个编码位 3 位（一次一个半字节）：
  y = 4 * ceil(log(x) / (3 * log(2)))
• 方案二，每个编码位1字节加分隔符：
  y = 9 * ceil(log(x) / (8 * log(2))) + 1
• 解决方案二，每个编码位 1 个半字节加分隔符：
  y = 5 * ceil(log(x) / (4 * log(2))) + 1

我建议您花时间绘制它们（最好使用对数线性坐标系查看）以获得适合您的情况的理想解决方案，因为没有完美的解决方案。我认为第一种方案的结果最稳定。