encoding - 编码随机可变长度二进制代码序列的最紧凑方法？

Question

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

我不关心读取或写入性能。我只想使用最少的空间。此外，示例是用 Java 编写的，但我们不限于 Java 系统。每个“列表”的长度是无限的。因此，任何对每个列表的长度进行编码的解决方案本身都必须对可变长度数据类型进行编码。

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

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

编辑

我不明白为什么很多答案都在谈论压缩。我并不是要进行压缩本身，而只是将随机的比特序列编码下来。除了每个位序列的长度不同并且需要保留顺序。

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

研究

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

结果

我将使用论文A new recursive universal code of the positive integers 中描述的 Elias Omega Coding的变体

我现在明白了较小整数的表示越小是如何与较大整数进行权衡的。通过简单地选择具有第一个整数的“大”表示的通用代码，从长远来看，当您需要对任意大整数进行编码时，您可以节省大量空间。

score 9 · Accepted Answer

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

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

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

附录

如果您想进一步微调 value 的长度，可以添加另一个存储 value 确切长度的字段。长度字段的长度可以由头的长度来确定。这是一个 9 位的示例。

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

score 7 · Accepted Answer

我对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>

4. 邮编

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

如果您的表示中有任何重复的模式（即使是您没有看到的），它应该能够压缩它。不过不要盲目相信它，请检查“压缩”形式是否比“未压缩”形式轻，但并非总是如此。

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，这确实看起来很浪费。然而，我不会试图猜测一旦压缩开始会发生什么。

您可能希望打包更多。如果我们放弃保留整个字节的想法，这是可能的......

保持长度编码不变（在整个字节上），但不要“填充” List<Boolean>. 一个元素列表变为0000 0001 x（9 位）
尝试“打包”长度编码

第二点更难，我们有效地归结为双倍长度编码：

表示多少位编码长度
实际上对这些位的长度进行编码

例如：

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

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

至于Elias omega coding，就更惨了。来自维基百科文章：

17 -> '10 100 10001 0'

就是这样，一个惊人的 11 位。

道德：您不能在不考虑手头数据的情况下选择编码方案。

所以，除非你List<Boolean>有数百个长度，否则不要打扰并坚持我的小建议。

score 4 · Accepted Answer

我会使用可变长度整数来编码要读取的位数。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

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

score 3 · Accepted Answer

我猜对于“可能最紧凑的方式”，您需要进行一些压缩，但霍夫曼编码可能不是可行的方法，因为我认为它最适合具有静态每个符号频率的字母表。

查看算术编码- 它对位进行操作并且可以适应动态输入概率。我还看到有一个 BSD 许可的Java 库可以为你做这件事，它似乎期望单个位作为输入。

我想为了实现最大压缩，您可以连接每个内部列表（以其长度为前缀）并在整个批次中再次运行编码算法。

score 3 · Accepted Answer

我看不出对任意一组位进行编码与压缩/编码任何其他形式的数据有何不同。请注意，您只对要编码的位施加了宽松的限制：即，它们是位列表的列表。有了这个小限制，这个比特列表就变成了数据，任意数据，这就是“正常”压缩算法压缩的内容。

当然，大多数压缩算法都假设输入在未来（或过去）以某种方式重复，如在 LZxx 系列压缩器中，或者具有给定的符号频率分布。

鉴于您的先决条件以及压缩算法的工作原理，我建议您执行以下操作：

使用尽可能少的字节数打包每个列表的位，使用字节作为位域，对长度进行编码等。
在生成的字节流上尝试霍夫曼、算术、LZxx 等。

有人可能会争辩说，这是一种非常明显和最简单的方法，并且由于您的位序列没有已知的模式，因此这不起作用。但事实是，这是在任何情况下都可以做到的最好的。

除非，你从你的数据中知道一些东西，或者对这些列表进行一些转换，使它们产生某种模式。以JPEG编码中DCT系数的编码为例。列出这些系数（对角线和之字形）的方式是为了有利于转换的不同系数的输出中的模式。通过这种方式，可以将传统压缩应用于生成的数据。如果您知道这些位列表中的某些内容，这些位列表允许您以更可压缩的方式重新排列它们（一种显示更多结构的方式），那么您将获得压缩。

score 3 · Accepted Answer

我有一个偷偷摸摸的怀疑，在最坏的情况下，您根本无法将真正随机的一组位编码为更紧凑的形式。任何类型的 RLE 都会在错误的输入上使集合膨胀，即使它在平均和最佳情况下都会做得很好。任何类型的周期性或内容特定的近似值都会丢失数据。

正如其他海报之一所说，您必须了解有关数据集的一些信息才能以更紧凑的形式表示它和/或您必须接受一些损失才能将其变成可以更紧凑地表达的可预测形式.

在我看来，这是一个具有无限信息和零损失约束的信息论问题。您不能以不同的方式表示信息，也不能将其近似为更容易表示的东西。因此，您需要的空间至少与您拥有的信息一样多，而且不少。

http://en.wikipedia.org/wiki/Information_theory

我想，你总是可以作弊，并操纵硬件对媒体上的离散值范围进行编码，以梳理出更多的“每比特比特”（想想多路复用）。不过，您会花费更多时间对其进行编码和阅读。

实际上，您总是可以尝试“抖动”效果，在这种效果中以多种方式（尝试解释为音频、视频、3d、周期性、顺序、基于键、差异等）和多种页面大小对数据进行多次编码并选择最好的。您几乎可以保证获得最佳的合理压缩，并且您的最坏情况不会比您的原始数据集更糟。

不知道这是否会让您获得理论上的最佳成绩。

score 2 · Accepted Answer

理论极限

如果不了解您打算压缩的数据的更多信息，这是一个很难回答的问题；对于不同的域，您的问题的答案可能会有所不同。

例如，来自维基百科关于无损压缩的文章的限制部分：

无损数据压缩算法不能保证所有输入数据集的压缩。换句话说，对于任何（无损）数据压缩算法，都会有一个输入数据集在算法处理时不会变小。使用计数参数的初等数学很容易证明这一点。...

基本上，由于理论上不可能无损地压缩所有可能的输入数据，因此甚至不可能有效地回答您的问题。

实际妥协

只需使用 Huffman、DEFLATE、7Z 或一些类似 ZIP 的现成压缩算法，并将这些位编码为可变长度字节数组（或列表、向量，或在 Java 或任何你喜欢的语言中调用的任何内容）。当然，要读回这些位可能需要一些解压缩，但这可以在幕后完成。您可以创建一个隐藏内部实现方法的类，以返回某个索引范围内的布尔值列表或数组，尽管数据内部存储在包字节数组中。在给定索引处更新布尔值可能是一个问题，但绝不是不可能的。

score 1 · Accepted Answer

List-of-Lists-of-Ints-Encoding：

当您来到列表的开头时，记下 ASCII '[' 的位。然后继续进入列表。
当您遇到任意二进制数时，请记下对应于 ASCII 中数字的十进制表示的位。比如数字100，写0x31 0x30 0x30。然后写入对应于 ASCII ',' 的位。
当您到达列表的末尾时，记下“]”的位。然后写 ASCII ','。

这种编码将对任意长度的无界整数列表的任意深度嵌套进行编码。如果此编码不够紧凑，请使用 gzip 跟进以消除 ASCII 位编码中的冗余。

score 0 · Accepted Answer

0

您可以将每个 List 转换为 BitSet，然后序列化 BitSet-s。

于 2010-01-29T19:10:27.090 回答

score 0 · Accepted Answer

好吧，首先，您需要将这些布尔值打包在一起，以便将其中的 8 个值合并到一个字节中。C++ 的标准位集就是为此目的而设计的。如果可以的话，您可能应该在本地使用它而不是矢量。

之后，理论上您可以在保存时压缩它以使尺寸更小。我建议不要这样做，除非你的背真的靠在墙上。

我说理论上是因为这在很大程度上取决于您的数据。在对您的数据一无所知的情况下，我真的不能再说什么了，因为某些算法在某些类型的数据上比其他算法更有效。事实上，简单信息论告诉我们，在某些情况下，任何压缩算法都会产生比您开始时占用更多空间的输出。

如果您的位集相当稀疏（不是很多 0，也不是很多 1），或者是条纹（相同值的长时间运行），那么您可能会通过压缩获得很大的收益。在几乎所有其他情况下，它都不值得麻烦。即使在这种情况下，也可能不是。请记住，您添加的任何代码都需要进行调试和维护。

score 0 · Accepted Answer

正如您所指出的，没有理由使用比单个位更多的空间来存储布尔值。如果将其与一些基本结构结合起来，例如每行以一个整数开头，该整数编码该行中的位数，您将能够存储任何大小的 2D 表，其中行中的每个条目都是一个位。

然而，这还不够。一串任意的 1 和 0 看起来相当随机，并且任何压缩算法都会随着数据随机性的增加而崩溃 - 所以我建议使用像 Burrows-Wheeler Block 排序这样的过程来大大增加重复的“单词”或“块”在您的数据中。一旦完成，一个简单的 Huffman 代码或 Lempel-Ziv 算法应该能够很好地压缩您的文件。

要使上述方法适用于无符号整数，您将使用 Delta 代码压缩整数，然后执行块排序和压缩（信息检索发布列表中的标准做法）。

score 0 · Accepted Answer

@zneak 的答案（击败我），但使用霍夫曼编码的整数，特别是如果某些长度更有可能。

只是为了自包含：将列表的数量编码为霍夫曼编码的整数，然后对于每个列表，将其位长编码为霍夫曼编码的整数。每个列表的位都紧随其后，没有中间浪费的位。

如果列表的顺序无关紧要，按长度排序会减少所需的空间，只需对每个后续列表的增量长度增加进行编码。

score 0 · Accepted Answer

如果我正确理解了这个问题，那么这些位是随机的，并且我们有一个独立随机长度列表的随机长度列表。由于没有什么可以处理字节，我将把它作为一个比特流来讨论。由于文件实际上包含字节，因此您需要为每个字节打包 8 位，并使最后一个字节的 0..7 位不使用。

存储布尔值的最有效方式是按原样存储。只需将它们作为简单数组转储到比特流中即可。

在比特流的开头，您需要对数组长度进行编码。有很多方法可以做到这一点，您可以通过选择最适合您的阵列的方式来节省一些位。为此，您可能希望使用带有固定码本的霍夫曼编码，以便常用和较小的值获得最短的序列。如果列表很长，您可能不会太在意它以更长的形式编码的大小。

如果没有关于预期列表长度的更多信息，就无法给出关于码本（以及哈夫曼码）将是什么的精确答案。

如果所有内部列表的大小相同（即您有一个二维数组），那么您当然只需要两个维度。

反序列化：解码长度并分配结构，然后逐个读取位，将它们按顺序分配给结构。

score 0 · Accepted Answer

List-of-List-of-Ints-binary：

Start traversing the input list
For each sublist:
    Output 0xFF 0xFE
    For each item in the sublist:
        Output the item as a stream of bits, LSB first.
          If the pattern 0xFF appears anywhere in the stream,
          replace it with 0xFF 0xFD in the output.
        Output 0xFF 0xFC

解码：

If the stream has ended then end any previous list and end reading.
Read bits from input stream. If pattern 0xFF is encountered, read the next 8 bits.
   If they are 0xFE, end any previous list and begin a new one.
   If they are 0xFD, assume that the value 0xFF has been read (discard the 0xFD)
   If they are 0xFC, end any current integer at the bit before the pattern, and begin reading a new one at the bit after the 0xFC.
   Otherwise indicate error.

score 0 · Accepted Answer

这个问题有一定的归纳感。您想要一个函数： (bool list list) -> (bool list) 使得反函数 (bool list) -> (bool list list) 生成相同的原始结构，并且编码的 bool 列表的长度最小，没有对输入结构施加限制。由于这个问题是如此抽象，我认为这些列表可能非常大——可能是 10 ^ 50，或者 10 ^ 2000，或者它们可能非常小，比如 10 ^ 0。此外，可能有大量列表，同样是 10^50 或只有 1 个。因此算法需要适应这些广泛不同的输入。

我在想我们可以将每个列表的长度编码为（bool 列表），并添加一个额外的 bool 来指示下一个序列是另一个（现在更大）长度还是真正的比特流。

让 encode2d(list1d::Bs) = encode1d(length(list1d), true) @ list1d @ encode2d(Bs)
    编码2d（无）=无

让 encode1d(1, nextIsValue) = true :: nextIsValue :: []
    编码1d(len, nextIsValue) =
               让 bitList = toBoolList(len) @ [nextIsValue] in
               编码1d（长度（位列表），假）@位列表

让 decode2d(位) =
               让 (list1d, rest) = decode1d(bits, 1) in
               list1d :: decode2d（休息）

让 decode1d(bits, n) =
               让长度 = fromBoolList(take(n, bits)) in
               让 nextIsValue :: bits' = skip(n, bits) in
               if nextIsValue then bits' else decode1d(bits', length)

假定的库函数
-------------------------

toBoolList : int -> bool 列表
   这个函数接受一个整数并产生布尔列表表示
   的位。所有前导零都被删除，除了输入“0”

fromBoolList : 布尔列表 -> int
   toBoolList 的倒数

采取： int * a' 列表 -> a' 列表
   返回列表的第一个 count 元素

跳过： int * a' 列表 -> a' 列表
   删除第一个 count 元素后返回列表的剩余部分

开销是每个单独的布尔列表。对于空列表，开销是 2 个额外的列表元素。对于 10^2000 个布尔值，开销将是 6645 + 14 + 5 + 4 + 3 + 2 = 6673 个额外的列表元素。

score 0 · Accepted Answer

如果我理解正确，我们的数据结构是 (1 2 (33483 7) 373404 9 (337652222 37333788))

格式如下：

byte 255 - escape code
byte 254 - begin block
byte 253 - list separator
byte 252 - end block

所以我们有：

 struct {
    int nmem; /* Won't overflow -- out of memory first */
    int kind; /* 0 = number, 1 = recurse */
    void *data; /* points to array of bytes for kind 0, array of bigdat for kind 1 */
 } bigdat;

 int serialize(FILE *f, struct bigdat *op) {
   int i;
   if (op->kind) {
      unsigned char *num = (char *)op->data;
      for (i = 0; i < op->nmem; i++) {
         if (num[i] >= 252)
            fputs(255, f);
         fputs(num[i], f);
      }
   } else {
      struct bigdat *blocks = (struct bigdat *)op->data
      fputs(254, f);
      for (i = 0; i < op->nmem; i++) {
          if (i) fputs(253, f);
          serialize(f, blocks[i]);
      }
      fputs(252, f);
 }

有一个关于数字数字分布的规律，对于任意无符号整数的集合，字节值越高，它发生的越少，所以在最后放置特殊代码。

在每个前面不编码长度占用的空间要少得多，但会使反序列化成为一项困难的练习。

encoding - 编码随机可变长度二进制代码序列的最紧凑方法？

研究

结果

16 回答 16

附录

Related

Reference