二进制运行长度编码

Question

我有一个Web表单,我希望在Base64中生成一个简短表示的内容.除其他外,表单包含264个二进制值的列表,其中大部分值在任何时候都将为0.(它们代表地理地图上的区域).即使在Base64中,这个264位数也会产生一个长而令人生畏的字符串.我想尽可能有效地实现行程编码.你能帮帮我吗？我用谷歌搜索了二进制RLE,但没有发现任何用处.

我尝试了这么多 - 使用十进制计数在二进制字符串上运行RLE,并使用"A"作为表示0和1之间的变化的分隔符,然后将结果从基数11转换为基数64.例如:

00000000001111111000000010000000000000000000000001111111110001111010101000000000000000000000000000000000000111111111110111000000000000111111100000001000000000000000000000000111111111000111101010100000000000000000000000000000000000011111111111011100

变

10A5A5AA22A7A1A2AAAAAAA34A9AA1A10A5A5AA22A7A1A2AAAAAAA34A9AA1A

而这反过来成为

CNnbr/FxkgbbOw0LNAKgk65P8SdvaTG+t74o

或者,在62号基地,

6imo7zq1pqr2mqglTHzXwJRAksm7fvHZHWQK

它更好,但我仍然不禁怀疑我做错了什么 - 使用数字"A"作为分隔符是最好的方法吗？

另一个更新:

感谢@comingstorm,我已经缩短了压缩字符串.

ILHHASCAASBYwwccDASYgAEgWDI=

正如我在评论中提到的那样,实际使用情况通常会导致更短的字符串.

Answer 1

由于您正在编码位,因此您可能希望使用基于位的RLE而不是基于字节的RLE.在这种情况下,您应该考虑使用Elias gamma编码(或其某些变体)来有效地编码运行长度.

您的编码格式的合理的第一个近似值可能是:

• 第一位=与未压缩字符串的第一位相同(设置初始极性)
• 剩余比特:Elias编码的连续比特运行长度(交替1和0)

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

请注意,游程长度"压缩"总是可以扩展您的位串; 如果您对此感到担心,可以添加另一个初始位来指示您的数据是处于压缩格式还是未压缩格式,从而将压缩开销限制为1位.