「ハフマン符号」の版間の差分
削除された内容 追加された内容
編集の要約なし |
編集の要約なし タグ: コメントアウト |
||
3行目:
|参照方法= 2011-9
}}
'''ハフマン符号'''（ハフマンふごう、'''Huffman coding'''）とは、[[1952年]]に{{仮リンク|デビット・ハフマン|en|David A. Huffman}}によって開発された符号で
ほかの[[エントロピー符号]]と同様、よく出現する文字には短いビット列を、あまり出現しない文字には長いビット列を割り当てることで、メッセージ全体の符号化に使われるデータ量を削減することを狙っている。
<!--▼
[[コンパクト符号]]や[[エントロピー符号]]の一つ。[[JPEG]]や[[ZIP]] ([[Deflate]]) などの圧縮フォーマットで使用されている。
[[シャノン符号化]]が最適ではない場合が存在する不完全な符号であったのに対し、ハフマン符号は（整数の符号語長という制約のもとでは、）常に最適な符号を構成できる。擬似的に実数の符号語長を割り振る[[算術符号]]と比較すれば、データ[[圧縮効率]]は劣る。ただし、算術符号やその他の高効率の符号化法と異なり、特許の問題が無い。
-->▼
<!--
==種類==
符号化の原理上、木を構成する前に各記号の出現頻度をあらかじめ知っておく必要がある。
15 ⟶ 22行目:
一方、最初の状態では頻度情報を持たず、記号を1個読み込むごとに符号木を作り直す方法は'''適応型ハフマン符号''' ('''[[:en:Adaptive Huffman coding|Adaptive Huffman coding]]''') である。これを指して日本では'''動的ハフマン符号'''と呼ぶことが多い。
-->
== 符号化の原理 ==
例として DAEBCBACBBBC という12文字からなるメッセージを考える。
このメッセージ中には５種類の文字が使われているので、もしそれぞれの文字を固定長のビット列で表すとすれば、１文字につき最低３ビット必要となる。
文字とビット列の対応表として、
A B C D E
000 001 010 011 100
を使い、それぞれの文字をビット列に置き換えたとすると、メッセージ全体は次のビット列で表される。
D A E B C B A C B B B C
011 000 100 001 010 001 000 010 001 001 001 010
12文字 x 3ビットで全体のビット数は36ビットとなる。
もし、よく出現する文字には短いビット列を、あまり出現しない文字には長いビット列を割り当てることができれば、メッセージ全体の符号化に必要なビット数を抑えることが期待できる。そこで、文字とビット列の対応表として、
A B C D E
110 0 10 1110 1110
を使ったとすると、メッセージ全体は
D A E B C B A C B B B C
1110 110 1110 0 10 0 110 10 0 0 0 10
となり、全体のビット数は25ビットとなる。
固定長の方式に比べると 70% ほどのデータ量に抑えられている。
=== ハフマン符号の構成 ===
文字とビット列の対応表を作るには、まずデータに出現する文字の出現回数を求め、それをもとにハフマン木と呼ばれる[[バイナリツリー]]を構成するという手順を踏む。
ハフマン木の構成の仕方は次のようなアルゴリズムになる。
#まず、葉を含むすべての節点のうち、親を持たないものを集める。
25 ⟶ 66行目:
以上を繰り返して根節点まで到達して木が完成される。次に、根から順に左右に0と1の値を割り振っていく（左右のどちらに0と1を与えるかは任意）。すると、それぞれの葉（記号）に対して、一意にビット列が与えられる。この記号とビット列の関係をもとに、もとのデータの記号をビット列に変換していくことで符号化が行われる。
=== 例 ===▼
▲<!--
=== 例 ===
[[画像:Huffman_tree.png|frame|ハフマン木]]
89 ⟶ 87行目:
が得られ、個数の多い文字ほど短い符号が割り当てられていることがわかる。
▲-->
=== 接頭符号 ===
ハフマン符号は接頭符号である。つまり、ある文字に対応するビット列が、他の文字に対応するビット列の接頭辞になることはない。この特徴のおかげで、デコーダはビット列を先頭から一度読むだけで元のメッセージを一意にデコードできる。
[[算術符号]]やその他の高効率の符号化法と異なり、特許の問題が無い。 そのため、[[JPEG]]や[[ZIP]]などの圧縮フォーマットで使用されている。
<!--
==実装==
[[Groovy]]で実装を説明する。まず、符号情報とハフマン木のクラスを作る。
157 ⟶ 162行目:
}
</source>
-->
== 関連項目 ==
* [[シャノン符号化]]
| |||