optimization - 编码 - 高效发送稀疏 bool 数组

Question

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

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

以下数字为近似值。

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

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，因此第二种解决方案更好。

有没有一种方法可以在不增加太多处理开销的情况下做得更好？

Answer 1

既然你说“实际上是随机分布的”，那么我们假设每个位置都是概率为 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，这将溢出您的表示。

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

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