binary - バイナリ ストリームのエントロピー エンコーディング

Question

バイナリ ストリームを圧縮したい。「1」の後に「0」を見つける確率が高くなり、「0」の後に「1」を見つける確率が高くなることがわかっています。どのようにエンコードすればよいですか？ライスコードについて考えていましたが、ここまでは行きませんでした... 返信ありがとうございます。

Answer 1

簡単なハフマンコーディングを試してみましたか? おそらくそれほど節約にはなりませんが、コード「10」と「01」のいずれかが「00」または「11」よりもはるかに高い確率を持っている場合は、それを「0」に再マッピングし、他のコードを「10」に再マッピングできます。 、「110」および「111」。

もちろん、ストリームを 2 ビットのチャンクに分割し、1 つのケースのみを最適化するため、これは最良の選択ではありません。ただし、4 ビットまたは 8 ビットなどのより大きな入力セットの確率を計算/測定することで精度を高めることができます。8 ビットの場合、10101010 および 01010101 が 00000000 および 11111111 よりも頻繁に使用されます。

算術コーディングや、ビット確率に基づくモデルを実際に使用する圧縮を使用すると、さらに良い結果が得られる場合があります。

もう 1 つの簡単な方法は、2 ビットごとに反転することです。あなたが言及する確率は、0101010 のような多くの交互のストリーム部分になる傾向があるため、通常は通常の圧縮アルゴリズムでより適切に圧縮できる 111111 のような多くのストリーム部分が得られます。しかし、この方法が成功するかどうかは、「確率のギャップ」が実際にどれだけ大きいかにかかっています。