compression - 短数字字符串的压缩

Question

有谁知道非常短的数字/二进制字符串的压缩？

例如，我想压缩任何数字（0-9）或二进制，即 3、2、6、4
，或者
我想压缩 2、1、3、6、1、4、13 的数字或二进制

适用于pick 4和euromillions的研究。

Answer 1

我查阅了 EuroMillions 和 Pick 4。我发现前者的范围是 1-50，而后者的范围是 0-9。我认为我们可以假设任何数字都是同样可能的（一些压缩方案利用了某些数字比其他数字更可能出现的事实）。

你在什么平台上编码？像 Python 或 JavaScript 这样的高级语言？还是像 C 或 C++ 这样的低级语言？您是否希望存储大量数字序列？或者你只是想提出一个有效的内存表示？

如果您想在内存中使用大型集合，您可以做出的最合理的权衡是确保每个字符由不超过 1 个字节表示（可以容纳 0-255 的值）。在通常只有“数字”类型而没有任何更细粒度的高级语言中，这可能更难做到。但是 C/C++ 甚至 Java 应该允许你这样做。

如果您想在磁盘上存储大量这些等概率数字，请查看存储数字所需的最小位数。对于 EuroMillions，您需要 6 位来存储一个数字 (2^6 = 64)。然后将它们存储在比特流中，以便每个数字节省 2 位。使用 Pick 4，您可以在一个字节中编码 2 个数字。