はふまんふごう
記号の出る確率をもとに、平均符号長が最小になる接頭符号を作る方法。確率の最も小さい2つの記号(または節)をまとめて1つにする操作を繰り返して木を作り、各分かれ目に0と1を割り当てて符号語とする。よく出る記号ほど短い符号語になる。1記号ずつ符号化する接頭符号の中では最適で、平均符号長はエントロピー以上、エントロピー + 1 ビット未満になる。ZIPやgzipのDeflate、JPEGなどで、ほかの方式と組み合わせて使われる。1952年にハフマンが発表した。
「ハフマン符号」は、1分野の5問の練習問題に出てきます(情報理論と符号の基礎など)。
この用語の分野: 情報理論と符号の基礎
例えば確率1/2、1/4、1/8、1/8の記号では、まず1/8どうしをまとめて1/4、次にそれと1/4をまとめて1/2、最後に残りの1/2とまとめます。根から各記号までの分かれ目に0と1を付けると、符号語は 0、10、110、111 になり、平均符号長は1.75ビットで、エントロピーと等しくなります。確率がすべて2のべき乗分の1のときは、このように平均符号長がエントロピーに一致します。
0と1の付け方や、等しい確率のどちらを先にまとめるかで、符号語は変わります。例えば確率0.4、0.2、0.2、0.1、0.1では、符号長が1、2、3、4、4にも、1、3、3、3、3にも、2、2、2、3、3にもなりますが、平均符号長はどれも2.2ビットです。そのため、試験などでは、符号語そのものより平均符号長を問うことが多くなります。
符号長は整数のビットに限られるので、確率が1に近い記号がある情報源では、エントロピーとの差が大きくなります。2値の記号を1つずつ符号化すると、どれほど偏っていても1記号に1ビットが必要です。記号をまとめて符号化するか、算術符号のように整数のビットに縛られない方式を使うと、エントロピーに近づけられます。
正解：A. 2.25ビット
まず0.1と0.15をまとめて0.25、次に0.2と0.25をまとめて0.45、残りの0.25と0.3をまとめて0.55、最後に0.45と0.55をまとめます。符号長はA、B、Cが2ビット、DとEが3ビットになり、平均符号長は (0.3 + 0.25 + 0.2) × 2 + (0.15 + 0.1) × 3 = 1.5 + 0.75 = 2.25 ビットです。確率の偏りが小さい情報源では、1、2、3、4、4 のような段々の符号長より、長さのそろった符号の方が短くなります。
どの記号にどの符号語を割り当てたか(符号表、または各記号の符号長)が必要です。そのため、圧縮したデータには符号表を添えるか、あらかじめ決めた表を使います。Deflateでは符号長だけを送り、受信側が同じ規則で符号語を作り直します(カノニカルハフマン符号)。
いいえ。記号の出る確率に偏りがなければ、ほとんど縮みません。例えば256種類のバイトがすべて等しい確率で出るデータでは、どの符号語も8ビットになり、符号表の分だけかえって大きくなります。
ハフマン符号では、確率の最も小さい2つをまとめる操作を繰り返します。
記号A、B、C、Dを確率0.4、0.3、0.2、0.1で、互いに独立に出す情報源を、ハフマン符号で符号化する。1記号あ…ハフマン符号では、0.1と0.3をまとめて0.4、次に0.4と0.6をまとめるので、符号長はAが1、BとCが2ビットです。
記号A、B、Cを確率0.6、0.3、0.1で、互いに独立に出す情報源があり、そのエントロピーは約1.30ビットである。…ZIPやgzipのDeflate方式は、LZ77で置き換えた結果を、さらにハフマン符号で符号化しています。
ZIPやgzipなどで使われるLZ77方式の考え方として、正しいものはどれか。Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。
平均符号長 情報エントロピー 可逆圧縮 クラフトの不等式 情報量 接頭符号 前方誤り訂正(FEC) 相互情報量 二元対称通信路 ハミング距離