math - 二进制游程长度编码

Question

我有一个 Web 表单，我想为其内容生成一个 Base64 的简短表示。除其他外，该表单包含 264 个二进制值的列表，其中大部分在任何时候都会为 0。 (它们代表地理 map 上的区域)。即使在 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 coding (或其某些变体)以有效地编码您的运行长度。

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

第一位=与未压缩字符串的第一位相同(设置初始极性)

剩余位:连续位运行的 Elias 编码长度(交替 1 和 0)

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

请注意，运行长度“压缩”始终可以扩展您的位串；如果您对此感到担心，您可以添加另一个初始位来指示您的数据是压缩格式还是未压缩格式，从而将压缩开销限制为 1 位。