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 であるため、2 番目のソリューションの方が適切です。

処理のオーバーヘッドをあまり追加せずに、これよりもうまくいく方法はありますか?

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 エントリの場合、現在、理論的に可能な 10.8 ビットではなく、1 回の実行あたり 20.5 ビットを費やしているため、その端に改善の可能性が最も高くなります。300 の場合: これらのシーケンスを表すのに十分なビットを予約していないと思います。エントロピーはピクセルあたり 9.23 ビットになり、現在 8 を送信しています。true の間のスペースが 256 を超える多くのケースが見つかり、表現がオーバーフローします。

もちろん、これはすべて、物事が本当にランダムであることを前提としています。そうでない場合は、別のエントロピー計算が必要です。いつでもヒストグラムを使用してデータから直接エントロピーを計算し、より複雑なオプションを追求する価値があるかどうかを判断できます。

最後に、実際のエントロピーコーダーはエントロピーを概算するだけであることにも注意してください。 たとえば、ハフマン符号化では、整数のビット数を各ランレングスに割り当てる必要があります。 算術符号化では、小数ビットを割り当てることができます。

于 2013-10-25T15:57:04.630 に答える