符号長の配列からハフマン木を生成する

　Ogg VorbisのCodebookで使う。自分用備忘録

・実例

　例えば、ハフマン符号の符号長が以下のように与えられたとする。

　ここから各値のハフマン符号を求める。

　まず、一番最初は符号長が2なので、符号は00で確定である。

　したがって、これ以降の符号で長さ2以上のものは01- から、また長さ2未満のものは 1- からしか始まることができない。

　次の符号長も2なので、01で確定する。この時点で、0- で始まる符号は枯渇したので、残りの符号はすべて 1- から始まる。
　一般に、符号の末尾が1ならば、その一つ上の枝に生える符号は枯渇しているので、枝を移動する必要がある。

　次の符号長は3なので、100になる。
　したがって、これ以降長さ3以上の符号は 101- から、長さ3未満のものは 11- から始まることになる。また、符号長1の符号はもはや取れないこともわかる。

　というようにして全部やっていくと、こうなる。

・一般化

　これをプログラムにしていく。ep[len]を、符号長がlenであるような符号の取りうる最小値とする。
　いま、符号長lenの符号cwが確定したとすると、このあと必要な処理は以下の2つ。

• (1)、j <= len であるようなjに対して、降順に(木の下から上に向かって)、
  • ep[j]の末尾が1でなければ、まだ枯渇していないので、ep[j]をインクリメントする。
  • ep[j]の末尾が1なら、もう枯渇しているので、枝を移動する(ep[j-1]と先頭が同じであるようにする)。枝を移動したら、そこより上の枝が同じ道の上にあるのは自明なので、そこで処理を切ってよい。
• (2)、j > len であるようなjに対して、昇順に、
  • ep[j]の先頭がcwと等しいとき、そのような符号は取れないので、枝を移動する。
  • そうでないなら、それ以降は符号が取れるので、そこで処理を切る。

　日本語が怪しい。説明下手。

・実装例

Javaで実装した。

public static int[] GenerateHuffmanTree(int[] l, int n) {
  int maxlen = 0;
  for (int i = 0; i < l.length; i++)
    maxlen = Math.max(l[i], maxlen);

  int[] ep = new int[maxlen + 1];
  int[] r = new int[n];

  for (int i = 0; i < n; i++) {
    int len = l[i];
    if (len > 0) {
      int cw = ep[len];
      if ((cw >>> len) != 0) {
        return null;
      }
      r[i] = cw;

      //(1)の処理
      for (int j = len; j > 0; j--) {
        if ((ep[j] & 1) != 0) {
          // have to jump branches
          if (j == 1)
            ep[1]++;
          else
            ep[j] = ep[j - 1] << 1;
          break;
          /* next upper ep[j] has already
             been on the same path */
        }
        ep[j]++;
      }
      //(2)の処理
      for (int j = len + 1; j <= maxlen; j++) {
        if ((ep[j] >>> ( len - j )) == cw) {
          ep[j] = ep[j - 1] << 1;
        } else {
          break;
        }
      }
    }
  }  
  return r;
}

　確率モデルはめんどくさい。