ハフマン符号の構成
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/09 01:48 UTC 版)
文字とビット列の対応表を作るには、まずデータに出現する文字の出現回数を求め、それをもとにハフマン木と呼ばれるバイナリツリーを構成するという手順を踏む。 ハフマン木の構成の仕方は、次のようなアルゴリズムになる。 まず、葉を含むすべての節点のうち、親を持たないものを集める。 その中から、最小の値を持つものと2番目に小さい値を持つものを取り出す。 それらを子供に持つ新しい節点を作る。このとき、新しい節点の値は、両方の子供の値の和とする。 以上を根節点に到達するまで繰り返すと、木が完成する。次に、根から順に左右に0と1の値を割り振っていく（左右のどちらに0と1を与えるかは任意）。すると、それぞれの葉（記号）に対して、一意にビット列が与えられる。この記号とビット列の関係をもとに、もとのデータの記号をビット列に変換していくことで符号化が行われる。
※この「ハフマン符号の構成」の解説は、「ハフマン符号」の解説の一部です。
「ハフマン符号の構成」を含む「ハフマン符号」の記事については、「ハフマン符号」の概要を参照ください。
ウィキペディア小見出し辞書の「ハフマン符号の構成」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- ハフマン符号の構成のページへのリンク
