有效包装编号

本文关键字：编号 包装 有效 | 更新日期: 2023-09-27 17:58:23

我的n数字在0..m-1的范围内。m不一定是2的幂。
将它们打包成字节流的最有效方法将需要精确地取整log2(m)*n位
我得到的数字是List<int>，m是int m。如何在不超过log2(m)*n/8大小的情况下将其打包到List<byte>中
包装完成后，如何才能取回具有List<byte>和int n, m的编号？

有效包装编号

家庭作业？

一般来说，当你在0..M-1范围内有N个数字时，这意味着你在0..M*N-1范围内有一个数字。表示这一点需要相等或更少的比特log2(M*N)，然后是单独编码数字的情况。

接下来，如果您对数字有其他了解（它们的分布，或者它们彼此之间的依赖性），您可以尝试应用各种压缩模式。当分布已知时，霍夫曼或类似的编码可能是最简单的方法。当序列依赖性已知时，LZ（W）或类似的方法将是可行的。等等。

编辑：回答评论中关于如何存储/写入/读取此类数字的问题。你可以用各种形式存储数字。字节数组似乎是最有效的方法之一（如果不是的话）。下面是一个关于如何使用BigInteger实现这一点的快速示例，它与字节数组的内存效率非常接近，但上面有一些方便的操作。您可能需要使用更合适的存储重新写入：

int[] Ms = new int[] { 10, 11, 12, 13 };
int N = 42;
System.Numerics.BigInteger x = new System.Numerics.BigInteger();
System.Numerics.BigInteger power = 1;
// composing the pack:
foreach (int s in Ms) {
    x += power * s;
    power *= N;
}
// reading the pack:
//  extracting i'th number:
int i = 2;
power = System.Numerics.BigInteger.Pow(N, i);
int result = (int)((x / power) % N);

将数字列表视为以m为基数的数字。

相关文章：