ハフマン符号
文字とビット列の対応表を作るには、まずデータに出現する文字の出現回数を求め、それをもとにハフマン木と呼ばれるバイナリツリーを構成するという手順を踏む。
ハフマン木の構成の仕方は、次のようなアルゴリズムになる。
まず、葉を含むすべての節点のうち、親を持たないものを集める。
その中から、最小の値を持つものと2番目に小さい値を持つものを取り出す。
それらを子供に持つ新しい節点を作る。このとき、新しい節点の値は、両方の子供の値の和とする。
以上を根節点に到達するまで繰り返すと、木が完成する。次に、根から順に左右に0と1の値を割り振っていく(左右のどちらに0と1を与えるかは任意)。すると、それぞれの葉(記号)に対して、一意にビット列が与えられる。この記号とビット列の関係をもとに、もとのデータの記号をビット列に変換していくことで符号化が行われる。