情報理論でのハフマン符号・・・？

質問

学校で情報理論を習っていて、
ハフマン符号化のやり方は、習いました。
　２元情報源を非等長でハフマン符号化は、
たとえば、0,1を確率0.8,0.2で発生する
記憶のない情報源ｓでは、確率の大きい0の
ランレングスを利用すれば、２元情報源を
ランレングスハフマン符号化すればできる
らしいのですが、
４元情報源を非等長でハフマン符号化をす
るのには、どうすれば分かりません。
２元と同じようにランレングスでできる
らしいのですが・・・。
　どなたかアドバイスお願いします。

回答No.3

Esna

こんにちは．Esnaです.

４元情報源でランレングス符号化してからハフマン符号化ということですか….

ランレングス符号化を行うと，t_amanoさんが言われたとおり，例えば，

aaaaabbccccdddaaa
5a2b4c3d3a

となります.組み合わせとしては，

自然数，記号，自然数，記号，…

となっています.
記号の部分には，確率によるハフマン符号を割り当てればいいと思いますが，自然数の部分をどのように表現するかが問題となります.
2パスで圧縮を行えば,出現した自然数の確率が求められますが,1パスの場合には,最大値が既知でないとハフマン符号は使えません.

2パスにしても,自然数の出現確率を使って,それをハフマン符号で表現する方法もありますし,自然数の部分をMH(Modified Huffman)のように64進法で表現して，ハフマン符号に変換する方法もあります.
1パスの場合には,Elias符号などを使う方法もあります.

回答になっているかわかりませんが，ごめんなさい.

回答No.2

t_amano

前の方もハフマンについて説明してますがもう少し単純にランレングスとハフマンの説明をします。
ランレングスは同じ記号が続く場合にその記号と個数の組み合わせで表現します。たとえばaaaaを4aとすると半分の容量で済みます。ただし同じ記号がほとんど続かないパターンだとかえって容量が増す場合もあるので圧縮にならないですね。
ハフマンは頻繁に出てくる記号を短いビット数の記号に割り当ててめったに出てこない記号を長いビット数に割り当てることで圧縮を可能にしてます。たとえばaという記号が頻繁に出てくる場合はaは通常1010の4ビットですがこれを0とすると1/4で済みます。
この二つは組み合わせて使用することも可能です。
この点を抑えて問題に取り組めばおのずと答えはでてくるのではないですか。がんばってください。

補足

ものすごく大切のことを書き忘れました。４元情報源をランレングスハフマン符号化をして＊２元＊の符号語にしなければならないということです。本当にごめんなさい。

回答No.1

Esna

こんにちは．Esnaです．

ハフマン符号化とランレングス符号化は，別物です．
ただ，ハフマン符号化は，記号に対して，それぞれ少なくとも１ビット以上の符号を割り当てるので，２元情報源の場合には，記号(１ビット)に１ビット以上の割り当てが行われるので，圧縮できないためランレングスを用いたのだと思います．
（ただし，数記号のブロック化を行えば別ですが…）

４元情報源の場合には，アルファベットが４種類あっておそらく出現確率が与えられていると思います．
ハフマン符号化の方法を習ったのであれば，ハフマン木の構成方法を習ったの思うのですが，それを適用すれば，ランレングスを用いなくても，構成できます．

例を示すと，記号a,b,c,dの出現確率がそれぞれ0.5,0.25,0.125,0.125とすると，
ハフマン木を構成し，木のパスに0,1を割り当てると，
(記号：ハフマン符号)
(a : 0)
(b : 10)
(c : 110)
(d : 111)
ができます．

補足

ランレングス符号化をおこなってからハフマン符号化をしてより効率的な符号をつくれという出題だったのです。説明不足みたいでごめんなさい。２元情報源（0,1）で長さ４までの符号化でなら1,01,001,0001としてそれぞれの確率を求めて、それをハフマン符号すればいいということは、わかるのですが、４元情報源（A,B,D,C）なら??? という状態でした。