7

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

我已经尝试了这么远- 使用十进制计数和“A”作为分隔符在二进制字符串上运行 RLE，表示 0 和 1 之间的变化，然后将结果从基数 11 转换为基数 64。例如：

00000000001111111000000010000000000000000000000001111111110001111010101000000000000000000000000000000000000111111111110111000000000000111111100000001000000000000000000000000111111111000111101010100000000000000000000000000000000000011111111111011100

变成

10A5A5AA22A7A1A2AAAAAAA34A9AA1A10A5A5AA22A7A1A2AAAAAAA34A9AA1A

这反过来变成

CNnbr/FxkgbbOw0LNAKgk65P8SdvaTG+t74o

或者，以 62 为基数，

6imo7zq1pqr2mqglTHzXwJRAksm7fvHZHWQK

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

另一个更新：

感谢@comingstorm，我又缩短了压缩字符串。

ILHHASCAASBYwwccDASYgAEgWDI=

正如我在评论中提到的那样，实际用例通常会导致字符串更短。

4

3 回答 3

9

由于您正在对位进行编码，因此您可能希望使用基于位的 RLE 而不是基于字节的 RLE。在这种情况下，您应该考虑使用Elias 伽马编码（或其一些变体）来有效地编码您的游程长度。

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

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

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

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

于 2011-09-29T22:13:19.233 回答
1

264 位，只有 33 字节，在 base64 中只有 44 字节。我认为这个（非常少的）信息量很难压缩。稀疏表示 nulvinge 也仅存储非零元素及其值（因为您只有 0/1），即在您的情况下只是非零位的索引。但是由于您有 264 位可能的位 - 您需要 9 位作为索引，这意味着，如果您有超过 29 个非零条目，则您需要的不仅仅是原始的。

也许您的问题表述错误，但我看不出 264 位如何导致令人生畏的 base64 字符串（您如何生成它 - 也许您翻译的不是 264 位，而是 264 个 ASCII 字符（带有值0和1） - 这可以解释你的长结果字符串？）。

于 2011-09-29T14:38:55.847 回答
0

我认为您想要的另一种选择是稀疏矩阵： http ://en.wikipedia.org/wiki/Sparse_matrix

于 2011-09-29T14:26:28.197 回答