バイナリストリームのエントロピー符号化

Question

バイナリストリームを圧縮したい。私は、各「1」の後に「0」を見つける可能性が高く、各「0」の後に「1」を見つける可能性が高いことを知っています。どのようにエンコードする必要がありますか？私はライスのコードについて考えていましたが、これまでには得られませんでした...どんな返事もありがとうございます。

Answer 1

シンプルなハフマンコーディングを試しましたか？おそらくそれはそれほど節約できませんが、コード '10'と '01'のいずれかが '00'または '11'よりもはるかに高い確率を持つ場合、 '0'に、 、 '110'、 '111'

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

算術符号化や実際にいくつかの圧縮を行うと、ビットの確率に基づいてより良い結果が得られる場合があります。

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