我有一个小范围内的 n 个整数序列，[0,k)并且所有整数都具有相同的频率f（因此序列的大小为n=f∗k）。我现在要做的是在提供随机访问的同时压缩这个序列（第 i 个整数是什么）。实现随机访问的时间不一定是 O(1)。我对以更高的随机访问时间为代价实现高压缩更感兴趣。
我没有尝试过霍夫曼编码，因为它根据频率分配代码（我所有的频率都是相同的）。对于这种特殊情况，也许我缺少一些简单的编码。
任何帮助或指示将不胜感激。
提前致谢。
PS：已经在 cs.stackexchange 中询问过，但在这里也询问更好的覆盖范围，抱歉。
如果所有整数都具有相同的频率，那么最佳压缩的公平近似值将是ceil(log2(k))每个整数的位数。您可以在恒定时间内访问这些位数组。
如果k非常小（如 3），则上述方法可能会浪费大量空间。但是，您可以将固定数量的小整数组合成一个k基数，这可以更有效地适合固定数量的位（您也可以方便地将结果放入标准大小的字中）。无论如何，您也可以在恒定时间内访问此编码。
如果您的整数没有相同的频率，则最佳压缩可能会从输入的不同部分产生可变的比特率，因此简单的数组访问将不起作用。在这种情况下，良好的随机访问性能需要索引结构：将压缩数据分成大小合适的块，每个块都可以按顺序解压缩，但这一次受块大小的限制。
如果每个数字的频率完全相同，则可以利用这一点节省一些空间——但这可能还不够值得。
n范围内随机数的熵[0,k)为n log2(k)，即log2(k)每个数字的位数；这是在不利用确切频率的情况下对数字进行编码所需的位数。
每个元素（其中）的f副本的可区分排列的熵是：kn=f*k
log2( n!/(f!)^k ) = log2(n!) - k * log2(f!)
应用斯特林近似（仅当n且f很大时才适用），产生：
~ n log2(n) - n log2(e) - k ( f log2(f) - f log2(e) )
= n log2(n) - n log2(e) - n log2(f) + n log2(e)
= n ( log2(n) - log2(f) )
= n log2(n/f)
= n log2(k)
这意味着，无论n大小k，您都不会通过利用输入的确切频率来获得大量空间。
上述斯特林近似的总误差是O(log2(n) + k log2(f))，它是O(log2(n)/n + log2(f)/f)按数字编码的。这确实意味着，如果您k的数据太大而f太小（即每个不同的数字只有少量副本），您可以通过巧妙的编码节省一些空间。但是，问题指定k实际上很小。
如果您计算出可能的不同组合的数量并取其对数基数 2，您可以找到最佳的压缩方式，我认为在您的情况下它不会那么好。对于频率为 1 的 16 个数字，可能的消息数为 16！Excel 告诉我以 2 为底，以 16 为底！是 44.25，而将它们存储为 4 位代码只需要 64 位。（您想要的每种类型都不止一种http://mathworld.wolfram.com/MultinomialCoefficient.html）
我认为您在将随机访问混入其中时会遇到问题，因为您拥有的唯一信息是每种类型的元素都有固定数量的元素 - 在整个序列中。对于整个序列来说，这并不是很多信息，而且它几乎没有单独说明序列的前半部分，因为你很可能在前半部分有更多的数字，而在后半部分则更少。