10月
28

ハフマンデコードテーブルのサイズ（その１）

梅澤 威志 技術ネタ 2013-10-28

単純なテーブル参照を繰り返すことによりハフマンデコードする場合のデコードテーブルのサイズについて考えてみる。

2014-01-19 更新: 証明を詰めて結論が変わりました。

まず、ハフマン符号に対する仮定は以下の通りとする（Ut Video Codec Suite で使われているものと同一）

  • シンボルは 8bit である。シンボル数 n \leq 256 である。必ずしも 256 ではないのは、出現しないシンボルは存在しないものとして扱うからである。
  • 符号語の長さの上限 L_{max} は 24 とする。
  • 長い符号語ほどゼロで始まる符号語を割り当てる。たとえば、符号語の長さの集合が 3, 3, 2, 1 の場合、000, 001, 01, 1 という符号語を割り当てる。

そして以下のようなアルゴリズムを考える（こちらは Ut Video Codec Suite で使われているものとは異なる）

符号列の先頭から m ビット見て、それでテーブルを lookup する。

  • もし先頭の符号語の長さが m ビット以下であったら、対応するシンボルが lookup により分かるためそこでデコードは完了し、次のシンボルに移る。
  • もし先頭の符号語が m ビットより長かったら、m ビットより長い符号語に共通の prefix の長さだけ読み飛ばし、また m ビット見て新たなテーブルを lookup する。以下繰り返し。

なお、m = 12 あたりを想定している。

さて、繰り返し回数 = テーブルの個数 の上限（あるいは上界）はいくつか、という事が気になる。

  • 上限が十分に小さいのであれば、最初からその上限固定サイズの構造体を使うことができる。
  • 上限が妥当に小さく大抵の場合は十分に小さいのであれば、とりあえず小さいテーブルを確保 (malloc) して必要に応じて拡張 (realloc) する方法を使うことができる。
  • 上限が妥当ではない大きさになってしまう場合、あるいは繰り返し回数が有限にならない場合は、このアルゴリズム自体をあきらめる必要がある。

定式化

L_i (0 \leq i < n) を各シンボルに対応する符号語の長さとする。 \sum 2^{-L_i} = 1 である。

m ビットより長い符号語に共通の prefix の長さが最大になるように符号語を割り当てているため、この prefix の長さ Lp = \left\lfloor - \log \sum \{ 2^{-L_i} | L_i > m \} \right\rfloor となる。 L_i も m も整数なので、 Lp = \left\lfloor - \log \sum \{ 2^{-L_i} | L_i \geq m + 1 \} \right\rfloor とも書ける。（注：情報科学の分野なので単に log と書いたら底は2である）

\sum \{ 2^{-L_i} | L_i \geq m + 1 \} < n 2^{-(m + 1)} なので、 - \log \sum \{ 2^{-L_i} | L_i \geq m + 1 \} > - \log n 2^{-(m + 1)} = m + 1 - \log n である。つまり、 Lp > \left\lfloor m + 1 - \log n \right\rfloor = m + 1 - \left\lceil \log n \right\rceil である。

なお、既に lookup を繰り返して q ビット読み飛ばしている状態にある場合、「q + m ビットより長い符号語に～」となるが、その場合 Lp > q + m + 1 - \left\lceil \log n \right\rceil になるので、追加で読み飛ばすビット数の下界は同じ式で表すことができる。

今、 n \leq 256, m = 12 を想定しているので Lp > 12 + 1 - \left\lceil \log 256 \right\rceil = 5 つまり Lp \geq 6 である。 L_{max} = 24 なので \left\lceil (24 - 12) / 6 \right\rceil + 1 = 3 がテーブル数の上界となる。

なお、8bit シンボル, m=12 でテーブル数3だとテーブルサイズは 2^12 * 2 * 3 = 24KB となって、最近の Intel CPU の1次キャッシュのサイズに近くなる。しかし、ほとんどの場合は最初のテーブルだけにアクセスし、後ろのテーブルほどアクセスされる確率が極端に小さくなるため、デコードテーブルによってキャッシュが圧迫される心配はしなくてよい。

Address: http://umezawa.dyndns.info/wordpress/?p=4334
«
»
Trackback

no comment untill now

Add your comment now