这个压缩算法有名称吗？

Question

假设你有一个四字节整数，你想要将它压缩为更少的字节。你可以进行压缩，因为小值的概率比大值更大（即，值越大，它的概率减小）。你使用以下方案，生成1、2、3或4个字节的结果：

请注意，在下面的描述中（位从最高有效位到最低有效位），即第一个位是最高有效位，第二个位是次高有效位等等...

1. 如果n<128，则将其编码为一个带有第一个位设置为零的单字节
2. 如果n>=128 and n<16,384，则使用两个字节整数。您将第一位设置为1，以表示此时使用两个字节。然后，将剩余的14位用于编码数字n。
3. 如果n>16,384 and n<2,097,152，则使用三个字节整数。您将第一位设置为1，表示使用三个字节；第二位设置为1，表示此时使用三个字节；第三位设置为0，不多解释。然后，使用剩余的21位来编码n。
4. 如果n>2,097,152 and n<268,435,456，则使用四字节整数。您将前三位设置为1，第四位设置为0，以表示使用四个字节。然后，使用剩余的28位来编码n。
5. 如果n>=268,435,456 and n<4,294,967,296，则使用五个字节整数。您将前四位设置为1，然后使用接下来的32位来设置n的确切值，作为一个四字节整数。其余的比特未使用。

这个算法有一个名称吗？

- Michael Goldshteyn

---

我喜欢这个想法！但是这会破坏指针的功能...指针必须读取所指向值的前几位，才能知道下一个值在哪里...不过这听起来确实很不错，我还没有听说过。 - user657496

这个方案与UTF-8非常相似。 - Jeffrey L Whitledge

我相信我曾经看过一个草案RFC，提议使用该方案传输任意精度整数，但我的Google技能失败了。无论如何，你不会获得专利 :) - Fred Foo

larsmans，请将您的评论提交为答案 - 如果您准确无误地击中了要害，您将获得勾选标记。 - Michael Goldshteyn

请查看：http://ebml.sourceforge.net/specs/ - sleeplessnerd

Answer 1

这与可变长度数量编码或基于128的编码非常接近。后者的名称源自于您的编码中的每个7位单位都可以视为基于128的数字。

- Fred Foo

---

如前所述，那不是真的。维基百科说3FFF的VLQ是“FF 7F”。使用@Michael Goldshteyn的算法，3FFF是“C0 3F FF”。 - ikegami

@ikegami：请重新阅读描述，你是对的：我错过了一些细节，包括长度是以基数1作为前缀而不是“穿过”整数表示的。 - Fred Foo

尽管larsmans的答案与我的算法不完全相同，但它符合问题的精神并且是最接近（实际存在的）算法。因此他获得了勾选标记。 - Michael Goldshteyn

Answer 2

这听起来与Dlugosz的可变长度整数编码非常相似。

- mohaps

---

这正是我所寻找的，但它并非由Dlugosz发明。larsmans在评论中发布了代码链接。 - Michael Goldshteyn

Answer 3

你的方案类似于UTF-8，这是一种用于Unicode文本数据的编码方案。

主要区别在于UTF-8流中的每个字节都指示它是前导字节还是尾随字节，因此可以从中间开始读取序列。而使用你的方案，如果存储了一系列这样的值，则缺少前导字节将使文件的其余部分完全无法读取。并且读取这样的序列必须从开头开始，而不是任意位置。

- Jeffrey L Whitledge

Answer 4

哈夫曼编码

哈夫曼编码是指为了储存更常见的数据而使用较少的位数，以换取使用更多的位数来储存不常见的数据。

- ikegami

---

不，这不是哈夫曼编码。从维基百科页面得知：哈夫曼编码使用特定方法为每个符号选择表示方式，从而产生前缀码（有时称为“前缀无码”，即“表示某个特定符号的位串从未是表示任何其他符号的位串的前缀”），它使用比较少见的源符号更短的位串表示最常见的源符号。 - Michael Goldshteyn

@Michael Goldshteyn，您指定使用某个值的概率与其大小成反比（越小，使用概率越大）。根据您的假设，该算法是一种哈夫曼编码形式。请注意，这是算法的一般类别，而不是您特定实现的名称。 - ikegami

不，我提出的算法属于熵编码类别，但它不是基于维基百科中任何定义/实现的哈夫曼编码形式。顺便说一句，你在答案中给出的哈夫曼编码定义适用于任何熵编码方案。 - Michael Goldshteyn

Answer 5

字节对齐的可变长度编码将值编码为整个字节的可变数量。其中最常见的是Varint，每个字节保留1位作为“连续位”。

特别是，对于任何格式，每个编码字节都有单个“连续位”长度位（加上7个数据位），可以创建一个相关格式，其中相同的位被重新组织成稍微不同的排列方式： 将所有长度信号位打包在开头（通常全部打包在第一个字节中）， 并将数据位打包到第一个字节的其余部分（如果还有空间的话）（以及后续字节的所有8位，如果有的话）。

许多人已经使用了这种位重新排列（有时与其他格式调整相结合）以加速解码，通常使用基于SIMD的算法，例如：“基于SIMD的发布列表解码”。

起始处的长度信号位：

“Imperial varint将所有连续位放在编码值的开头。”

Carl Mastrangelo:让我们制作一个Varint

"Group Varint Encoding"进一步说明： 单字节前缀存储以下4个整数值的2位“长度”。 也称为varint-GB。

Stream VByte甚至更进一步，将所有“长度”存储在一个位置，并将所有数据字节存储在另一个位置。

Varint：每个字节上的长度信号位

使用每个字节的高位来表示“继续”或“停止”，并将序列中每个字节的剩余7位解释为编码实际值的纯二进制：

这听起来像是Google Protocol Buffers中使用的“Base 128 Varint”。

压缩整数的相关方法

总之，此代码将整数分为两部分： 第一部分是一种一元编码，用于指示需要多少位来读取其余的值，第二部分（以指定的位宽）则是更或多或少的纯二进制，用于编码实际值。

这个特定的代码将一元编码与二进制编码“穿插”在一起，但其他类似的代码会先打包完整的一元编码，然后再打包二进制编码， 例如Elias gamma coding。

我怀疑这个代码是“开始/停止代码”家族中的一个， 如下所述：

Steven Pigeon - 开始/停止代码 - Procs. 数据压缩会议2001，IEEE计算机学会出版社，2001年。

- David Cary

---

varint是一种使用每个字节1位的编码方式，最后一个字节的高位为0。这种编码方式将长度标识位放在开头，因此全部位于第一个字节中。因此，解码可能更便宜，只需将第一个零的位置映射到移位计数和掩码，如果您从第一个字节开始加载4或8字节块。 - Peter Cordes