2

我有一个 256 x 256 布尔数组。这些数组不断变化，设置位实际上是随机分布的。

我需要在许多客户请求时将设置位的当前列表发送给他们。

以下数字是近似值。

如果我发送每个设置位的坐标：

set bits    data transfer (bytes)
    0            0
  100          200
  300          600
  500         1000
 1000         2000

如果我将距离（从左到右扫描）发送到下一个设置位：

set bits    data transfer (bytes)
   0             0
  100          256
  300          300
  500          500
 1000         1000

在这个稀疏数组中设置的典型位数约为 300-500，因此第二种解决方案更好。

有没有办法在不增加太多处理开销的情况下做得比这更好？

4

1 回答 1

2

既然您说“实际上是随机分布的”，那么我们假设每个位置都是概率为 p 的伯努利试验。选择 p 以获得您期望的填充率。您可以将“运行”的长度（您的选项 2）视为获得成功所需的伯努利试验次数。事实证明，这个试验次数遵循几何分布（概率为 p）。 http://en.wikipedia.org/wiki/Geometric_distribution

到目前为止，您在选项#2 中所做的是识别 p 的每种情况下运行的最大长度，并保留那么多位来发送所有这些。请注意，这个最大长度仍然只是一个概率，如果你真的很不走运，那么这个方案就会失败，并且你的所有位都聚集在开头和结尾。

正如@Mike Dunlavey 在评论中建议的那样，霍夫曼编码或其他形式的熵编码可以根据长度的频率重新分配花费的比特。也就是说，短期运行更为常见，因此使用更少的位来发送这些长度。这种编码效率的理论限制是分布的“熵”，您可以在该维基百科页面上查找它，并评估不同的概率。在您的情况下，此熵的范围从每次运行 7.5 位（对于 1000 个条目）到每次运行 10.8 位（对于 100）。

实际上，这意味着您不能比目前为 1000 个条目的情况做得更好。8 位 = 每个值 1 个字节。对于 100 个条目的情况，您当前每次运行花费 20.5 位而不是理论上可能的 10.8 位，因此该端具有最高的改进机会。在 300 的情况下：我认为您没有保留足够的位来表示这些序列。熵为每像素 9.23 位，而您当前发送的是 8 位。您会发现很多情况下 true 之间的空间超过 256，这会溢出您的表示。

当然，所有这些都假设事情确实是随机的。如果不是，则需要不同的熵计算。您始终可以使用直方图直接从数据中计算熵，并决定是否值得采用更复杂的选项。

最后，还要注意现实生活中的熵编码器只是近似熵。 例如，霍夫曼编码必须为每个游程长度分配整数位数。 算术编码可以分配小数位。

于 2013-10-25T15:57:04.630 回答