如何压缩一个非重复数字大小为N位的序列？
How to compress a sequence of non-repeated number size N bits?
我正在尝试压缩一系列非负数，其中：
- 每个数字的取值范围是0到2^N-1
每个数字只出现一次（表示共有2^N个数字）
N = 4 的示例：
[14, 1, 8, 2, 12, 6, 0, 10, 4, 13, 5, 7, 15, 9, 3, 11]
所以通常每个数字将花费 4 位，对于 16 个数字，我们将不得不使用 16x4 = 64 位来存储它们。
目前我只是想压缩它们如下：
- 对于前 8 个数字 --> 使用 4 位存储每个数字。
- 接下来的4个号码--->只有3个bits/each
- 接下来的2个号码--->只有2个bits/each
- 对于接下来的 1 个数字 ---> 只有 1 位。
- 对于最后一个，其实是没有必要存储的（显然如果我们知道其他15个数字我们应该知道最后一个数字是多少）
所以压缩后的数据大小为：
Z = 8 * 4 + 4 * 3 + 2 * 2 + 1 * 1 + 1 * 0 = 49 bits
压缩率76%左右，已经很不错了（我觉得）。
但对于较大的N值，该比率似乎有所降低（对于N = 2048，该比率仅为91%）
所以我想听听您对更好压缩的建议。
谢谢。
对于这个特定问题，最有效的编码是将 [0 .. 2^N-1] 的排列视为该排列的 factorial number system and store the Lehmer code 中的数字。
这给出了 ceil(log2((2^N)!)) 位的要求。对于 N = 4，这使用 45 位 (70.3%)；对于 N = 11 (2^N = 2048)，19581 位 (86.9%)。
压缩率随着N的增加而变差；使用简单的近似值 log x! >= (x log x) - x + 1 我们获得了 log2((2^N)!) / (N 2^N) 的最小值 1 - ((2^N - 1)/(2^N))*(1 / (N * log(2)))，它接近 1 因为 N 趋于无穷大。
考虑到压缩率的绝对限制，您可以找到任何合理有效的方法都值得一试；对于小到 N = 15 的值，不可能比 90% 做得更好。
目前您正在使用 N*2^N 位。
基本上你拥有的是数字的排列，每个排列都是唯一的，对于排列你可以计算一个唯一的标识符。因为有 (2^N)!排列，你只需要 ceil(log2((2^N)!)) 位。例如，这是 45 位。
正如评论中指出的那样，最佳编码（如果所有排列的概率均等）是用排列枚举中的索引替换整个排列。既然有n个！可能的排列，索引需要log2n！位，因此对每个元素使用 log2n 位的原始编码的压缩比是 (log n!)/(n log n).
使用Stirling's approximation，我们可以将其重写为 (n log n - n + O(log n))/(n log n), 即 1 - 1/(log n) + O(1/n) 显然渐近接近 1 作为 n[=35= 】 成长。所以较大的n.
压缩率下降是必然的
不可能实现更好的压缩，除非不是所有的排列都是等概率的（并且您有一些关于概率分布的信息）。
我正在尝试压缩一系列非负数，其中：
- 每个数字的取值范围是0到2^N-1
每个数字只出现一次（表示共有2^N个数字）
N = 4 的示例：
[14, 1, 8, 2, 12, 6, 0, 10, 4, 13, 5, 7, 15, 9, 3, 11]
所以通常每个数字将花费 4 位，对于 16 个数字，我们将不得不使用 16x4 = 64 位来存储它们。
目前我只是想压缩它们如下：
- 对于前 8 个数字 --> 使用 4 位存储每个数字。
- 接下来的4个号码--->只有3个bits/each
- 接下来的2个号码--->只有2个bits/each
- 对于接下来的 1 个数字 ---> 只有 1 位。
- 对于最后一个，其实是没有必要存储的（显然如果我们知道其他15个数字我们应该知道最后一个数字是多少）
所以压缩后的数据大小为：
Z = 8 * 4 + 4 * 3 + 2 * 2 + 1 * 1 + 1 * 0 = 49 bits
压缩率76%左右，已经很不错了（我觉得）。
但对于较大的N值，该比率似乎有所降低（对于N = 2048，该比率仅为91%）
所以我想听听您对更好压缩的建议。
谢谢。
对于这个特定问题，最有效的编码是将 [0 .. 2^N-1] 的排列视为该排列的 factorial number system and store the Lehmer code 中的数字。
这给出了 ceil(log2((2^N)!)) 位的要求。对于 N = 4，这使用 45 位 (70.3%)；对于 N = 11 (2^N = 2048)，19581 位 (86.9%)。
压缩率随着N的增加而变差；使用简单的近似值 log x! >= (x log x) - x + 1 我们获得了 log2((2^N)!) / (N 2^N) 的最小值 1 - ((2^N - 1)/(2^N))*(1 / (N * log(2)))，它接近 1 因为 N 趋于无穷大。
考虑到压缩率的绝对限制，您可以找到任何合理有效的方法都值得一试；对于小到 N = 15 的值，不可能比 90% 做得更好。
目前您正在使用 N*2^N 位。
基本上你拥有的是数字的排列，每个排列都是唯一的，对于排列你可以计算一个唯一的标识符。因为有 (2^N)!排列，你只需要 ceil(log2((2^N)!)) 位。例如，这是 45 位。
正如评论中指出的那样，最佳编码（如果所有排列的概率均等）是用排列枚举中的索引替换整个排列。既然有n个！可能的排列，索引需要log2n！位，因此对每个元素使用 log2n 位的原始编码的压缩比是 (log n!)/(n log n).
使用Stirling's approximation，我们可以将其重写为 (n log n - n + O(log n))/(n log n), 即 1 - 1/(log n) + O(1/n) 显然渐近接近 1 作为 n[=35= 】 成长。所以较大的n.
压缩率下降是必然的不可能实现更好的压缩，除非不是所有的排列都是等概率的（并且您有一些关于概率分布的信息）。