0から64の間の2つの位置をエンコードする最も効率的な方法は？

Question

データが含まれている中間部分のみにデータの前後がゼロであるという事実を利用して、圧縮したい64ビット値があります。

実際のデータの長さはlビットで、n + l + m = 64になるように、前にn 0、最後にm 0をパディングするとします。64ビットを送信/保存する代わりに、lビットに加えて、 64ビット間隔でデータの位置をエンコードする必要があります。

たとえば、l、m、およびデータビットを保存していた場合、lを読み取り、lビットのデータを読み取り、mを読み取り、データをmビット左にシフトすることにより、元の64ビットパターンを復元します。

私が思いつく最小のオーバーヘッドは、l、n、mのいずれか2つを格納するための6ビットの2倍です（それぞれ0から64の間）。その数を減らすことは可能ですか？

Answer 1

lは0から64までです。したがって、lを送信せず、nとmを送信します。両方ともゼロになる可能性があり、64に達する必要がないためです（単純に追加できる必要があります） 64）。

lビットは1で開始および終了する必要があるため、送信する必要はありません。

nに6ビットを送信
mに対して最大6ビットを送信します（以下を参照）
計算l = 64-（n + m）
l = 0の場合、数値は0です。他には何も送信しません
l = 1の場合、数値は1 * 2 ^ mであり、他には何も送信しません
l = 2の場合、数は3 * 2 ^ mであり、何も送信しない
中間のl-2ビットを送信します。

最大オーバーヘッド= 10ビット。

mのビットの削減は、
n <！> gt;の場合32それなら、m <！> lt; 32、したがって5ビットのみが必要です
n <！> gt;の場合48それならm <！> lt; 16、したがって4ビットのみが必要です
n <！> gt;の場合56すると、m <！> lt; 8、したがって3ビットのみが必要です
n <！> gt;の場合60それから、m <！> lt; 4、2ビットのみ必要です
n = 63の場合、m <！> lt; 2、1ビットで十分です

Answer 2

あなたの分析は、単一の称賛にふさわしいと思われます。しかし、このような値を大量に送信する場合、gzipのような一般的なエントロピーエンコーディングアルゴリズムは、ゼロの文字列を非常にうまく排除し、データの冗長性を活用できるため、おそらくより良いでしょう。

Answer 3

問題を述べたように、あなたが提案した解決策より良いことはできません。

ただし、数値のゼロの分布が歪んでいる場合は、ハフマンコードまたは同様の手法を使用してカウントを表すことにより、平均してより良い圧縮を得ることができます。別の可能性は、ゼロ分布が1つの64ビット値から次の値に強く相関している場合、デルタコーディングを使用することです。

いずれの場合も、可変ビット数を使用してゼロの数を表す必要があります。また、歪度や相関に関する仮定が間違っていると判明した場合、単純な方法で行った場合よりも平均して多くのビットを使用することになります。

Answer 4

あなたの解決策はかなり良いようです。
ハフマンコーディングは、特に頻度の高い値がある場合に値を圧縮するもう1つの方法です。

実装するのはそれほど難しくありませんが、送信するデータがあまりない場合は圧倒されるかもしれません。

Answer 5

64 1のシーケンスの開始位置nがあり、シーケンスの長さlは64 - nを超えることはできません。

r = sum(n = 0..63, 64 - n) + 1

シーケンスの合計。追加されたものは、すべてゼロのシーケンス用です。いくつかの計算を行うと、次の結果が得られます。

r = 64 * 64 - (63 * 64) / 2 + 1
  = 2081

2081の可能な値を表すには、log2(2081) = 11.023ビットが必要です。したがって、合計で6ビットを必要とする2つの12ビット番号を使用して情報をエンコードすることをお勧めします（可能なすべての値が均等に分布しているという仮定の下で）。