logo标签列表

二进制游程长度编码

mathbinarycompressionrun-length-encoding
7
我有一个网页表单，我想生成一个Base64的短表示。该表单包含264个二进制值的列表，其中大部分在任何单个时刻都将为0（它们代表地理地图上的区域）。即使是在Base64中，这264位数字也会生成一个长而令人生畏的字符串。我希望尽可能高效地实现游程编码。你能帮我吗？我已经在谷歌上搜索了二进制RLE，但没有找到有用的结果。
目前为止我尝试过的方法是使用十进制计数和"A"作为分隔符来运行RLE，表示0和1之间的变化，然后将结果从11进制转换为64进制。例如：
00000000001111111000000010000000000000000000000001111111110001111010101000000000000000000000000000000000000111111111110111000000000000111111100000001000000000000000000000000111111111000111101010100000000000000000000000000000000000011111111111011100

变成

10A5A5AA22A7A1A2AAAAAAA34A9AA1A10A5A5AA22A7A1A2AAAAAAA34A9AA1A

转而成为

CNnbr/FxkgbbOw0LNAKgk65P8SdvaTG+t74o

或者，在62进制中，

6imo7zq1pqr2mqglTHzXwJRAksm7fvHZHWQK

虽然现在更好了，但我仍然怀疑自己是否有做错什么——使用数字"A"作为分隔符是否是最好的方法？

另外一个更新:

感谢@comingstorm，我已经进一步缩短了压缩字符串。

ILHHASCAASBYwwccDASYgAEgWDI=

如我在评论中所提到的，实际使用情况通常会导致更短的字符串。

3个回答
10

由于你正在编码位，所以你可能希望使用基于位的RLE而不是基于字节的RLE。在这种情况下，你应该考虑使用Elias gamma coding（或其某个变体）来高效地编码您的运行长度。

对于您的编码格式，一个合理的第一个近似值可能是：

  • 第一个比特（bit）= 与未压缩字符串的第一位相同（以设置初始极性）
  • 其余比特：连续位运行的Elias编码长度（交替使用1和0）

由于您知道未压缩字符串中有多少位，因此您不需要终止代码；您可以添加任何必要的二进制填充作为任意位数。

请注意，运行长度“压缩”始终可能会扩展您的比特字符串；如果您担心这一点，您可以添加另一个初始位来指示数据是压缩还是未压缩格式，将压缩开销限制为1位。

1

264位，仅33字节，在base64中仅为44字节。我认为这（非常小的）信息量几乎无法压缩。Nulvinge提到的稀疏表示仅存储非零元素及其值（因为您只有0/1），即在您的情况下仅存储非零位的索引。但是，由于您有264个可能的位 - 您需要9位用于索引，这意味着如果您有超过29个非零条目，则需要比原始值更多。

也许您的问题表述不正确，但我不明白如何将264位转换为令人生畏的base64字符串（您是如何生成它的 - 也许您没有转换264位，而是264个ASCII字符（具有值0和1） - 这可以解释您的结果字符串很长的原因？）。

@egasimus：你说得对，我计算时考虑到了字大小。但是即使是 44 字节，这个通用语句也适用：太小无法很好地压缩它。 - flolo
好的，我已经设法删减了一些字母，请参见上文。上面的二进制数实际上是相当不太可能的输入数据。在更现实的情况下，它会变得更短。但我不确定是否应该使用“A”。 - avramov
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接