整数序列的压缩以提供随机访问

Question

整数序列的压缩以提供随机访问

4

我有一组n个整数，范围很小，为[0,k)，所有整数的频率都是相同的，为f（因此序列的大小为n=f∗k）。我现在正在尝试压缩该序列，同时提供随机访问（第i个整数是多少）。完成随机访问的时间不必是O(1)。我更感兴趣的是通过牺牲更高的随机访问时间来实现更高的压缩率。

我没有尝试使用哈夫曼编码，因为它是根据频率分配代码的（而我所有的频率都是相同的）。也许我错过了这种特殊情况的某些简单编码方式。

非常感谢您的帮助和指导。

PS：我已经在cs.stackexchange上发布过问题，但在此也发布一下，以获得更好的覆盖范围，抱歉。

- jplot

2

如果序列是真正的随机序列，那么你几乎无法对其进行压缩。你可以使用每个整数的log2(k)位的最小表示，但除此之外，你就要受到熵的影响了。 - evil otto

2

@evilotto：整数范围在[0，k)内，因此它们已经处于最小尺寸表示。但是我们并不是在谈论任意随机序列，因为它们全部具有完全相同的频率。 - Jon

1

如果 k = 256 并且数据完全随机，我会期望每个数值（大部分？）具有相同的频率。考虑到每个整数的8位表示，我认为它是不可压缩的，除非有其他冗余源。 - Dave Rager

1

因此，分布不是随机的（每个数字相同的频率），但顺序是随机还是结构化的呢？例如0 0 0 0 1 1 1 1 2 2 2 2是可压缩的，但真正随机的重排列则不太可能（至少从长远来看）。流中的结构潜在地可以导致比仅考虑频率更多的压缩，即使在极度偏斜的分布中也是如此。 - twalberg

@jkraju 公式为对所有c求和 n_c / n * lg(n / n_c)，其中n_c是c的频率，而n是序列长度。在此情况下，对所有c来说n_c是n / k。 - jplot

显示剩余6条评论

2个回答

1

如果你计算可能的不同组合数量并以2为底取对数，你可以找到最佳的压缩方式，但我认为在你的情况下效果不会太好。有16个频率为1的数字，可能的消息数量是16！Excel告诉我16！的以2为底的对数是44.25，而将它们存储为4位代码只需要64位。（当其中有多个相同元素时，您可以参考这里：http://mathworld.wolfram.com/MultinomialCoefficient.html）

我认为你在混合随机访问时会遇到问题，因为你唯一拥有的信息是每种元素的固定数量 - 在整个序列中。这对于整个序列来说并不是很多信息，并且对于隔离的序列的前半部分几乎没有任何作用，因为你在第一半部分可能有更多的某些数字，在第二半部分则可能较少。

- mcdowella

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- comingstorm · Accepted Answer

如果你所有的整数具有相同的频率，则最优压缩的公平近似值为每个整数 ceil(log2(k)) 位。你可以在常数时间内访问这些位数组。

如果 k 足够小而使用上述方法会浪费大量空间，但是你可以将一定数量的小整数组合成一个基于 k 的数字，这样可以更有效地将它们存储在固定位数的比特中（你可能还可以方便地将结果装入标准大小的字）。无论如何，你也可以在常数时间内访问此编码。

如果你的整数的频率不同，则最优压缩可能会从输入的不同部分产生可变的数据位速率，因此简单的数组访问将无法使用。在这种情况下，良好的随机访问性能需要索引结构：将你的压缩数据分解成方便大小的块，每个块可以按顺序进行解压缩，但是时间受限于块大小。

如果每个数字的频率恰好相同，则你可以通过利用这一点来节省一些空间，但这可能并不值得。

在范围 [0,k) 中的 n 个随机数的熵为n log2(k)，即每个数字需要 log2(k) 位的比特来编码你的数字，而不需要 利用确切的频率。

在每个元素中有f 个副本且元素为 k 的可区分排列的熵（其中 n=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很小，利用输入的确切频率不会获得大量空间。

上述Stirling近似的总误差为O(log2(n) + k log2(f))，每个编码数字为O(log2(n)/n + log2(f)/f)。这意味着，如果你的k很大，而你的f很小（即每个不同的数字只有少量副本），你可能可以通过巧妙的编码节省一些空间。然而，问题指定了k实际上是很小的。