Huffman木

• Huffman木とは
  • ある電子データの圧縮に際して用いるもので、N個の文字コードのデータ中の出現頻度の高低を集計し、その情報に基づいてN個の文字コードをN個の葉とするトーナメント樹のこと。この圧縮法では、作成したトーナメント樹の構造をもとに、通常用いる文字コードよりも桁数の小さい文字コードを作成する。トーナメント樹における葉ノードの位置が文字コードを表している。高頻度で出現する文字コードには少ない桁数を、低頻度で出現する文字コードには多い桁数での表現が割り当てられる。
• 樹の特徴
  • 2分岐木
  • N個の文字コードからは、N個の葉(末端ノード)と、N-1個の非葉ノード(根および節)からなる
  • 2分岐の方向(左下向きか右下向きか)には上下関係がある
• 木情報蓄積
  • 3つの要素数2N-1の整数アレイで全情報を格納する
    • parent[2N-1]
      • 2N-1個のノードの個々のノードの親に当たるノードIDを格納する
        • ただし、ノードが親にとって左下向きの子になっている場合は、parent[i]=k (kは親ノードID)、右下向きの子になっている場合は、parent[i]=-kとすることで、情報の劣化を防ぐ
    • left[2N-1]
      • 2N-1個のノードの個々のノードの左下向きの子のノードIDを格納する
    • right[2N-1]
      • 2N-1個のノードの個々のノードの右下向きの子のノードIDを格納する
• 木情報のハンドリング
  • 子方向探索
    • 以前書いた紹介記事の『Javaによるアルゴリズム事典』

      Javaによるアルゴリズム事典

      のHuffman法中に記載されているwritetree関数を参照(ソースもwebから取得可能→こちら)
    • 次のような再帰的関数を用いる
      • 引数として探索の親元のノードxを受け取る
      • 引数ノードの子をleft[x],right[x]として見いだす
        • 引数ノードに子がいなければ、探索終了
        • 引数ノードに子がいれば、その子をこの再帰的関数に引数として渡す