bzip2を読む ハフマン符号4

こんにちは、junkawaです。

本記事では、複数のハフマンテーブルを用いて符号化を行うマルチプルハフマン符号(Multiple Huffman Code)の初期化処理について、ソースコードを用いて紹介します。

対象の関数は、sendMTFValues() @ compress.c です。

これまでの流れ

入力データをブロックソートし、MTF変換する所まで紹介しました。また、ハフマン符号化の処理について紹介しました。

本記事からは、MTF変換後のデータをハフマン符号化する処理について紹介していきます。

bzip2のハフマン符号化では、複数のハフマンテーブルを用いて符号化を行うマルチプルハフマン符号(Multiple Huffman Code)を行います。

最大6個のハフマンテーブルを使用します。

符号化対象のデータ(MTF変換後のデータ)を50バイトのブロックに区切り、それぞれのブロックにハフマンテーブルを割り当てます。

通常のハフマン符号化では、データに対して一つの最適なハフマンテーブルが生成されます。

マルチプルハフマン符号化では、どのブロック間で同じハフマンテーブルを共有するか、の組み合わせによって、データ全体の圧縮率が変わってきます。

シンボルの出現頻度が同じ傾向を持つブロック間でハフマンテーブルを共有した場合、そうでない場合に比べて圧縮率は向上します。

bzip2では、ハフマンテーブル共有の組み合わせをヒューリスティックに改善していきます。最適な組み合わせではないですが、圧縮時間との兼ね合いで、そこそこ圧縮率がよい組み合わせを探索します。

ヒューリスティックアルゴリズム
https://ja.wikipedia.org/wiki/%E8%BF%91%E4%BC%BC%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

本記事では、ハフマンテーブル(カノニカルハフマンにおいてはハフマンテーブルが決まる=符号長が決まる、なので符号長)の初期化を行います。

ハフマンテーブルの初期値には、ハフマンテーブル毎に特定のシンボルを短く符号化できるように偏りをもたせます。

この初期値は、後段のテーブル割当の改善段階の1回目に、各ブロックにどのハフマンテーブルを割り当てるかの指標となります。改善段階の2回目は、1回目の割当結果を指標にします。

初期値の実装については、下記の文献を参考にしていると思われるのですが、文献を見つけることができなかったため詳細は不明です。

David J. Wheeler
Program bred3.c and accompanying document bred3.ps.
This contains the idea behind the multi-table Huffman coding scheme.
ftp://ftp.cl.cam.ac.uk/users/djw3/
参考： http://www.bzip.org/1.0.5/bzip2-manual-1.0.5.html#reading

コードの紹介

sendMTFValues() @ compress.c
https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/compress.c#L239

  234: /*---------------------------------------------------*/
  235: #define BZ_LESSER_ICOST  0
  236: #define BZ_GREATER_ICOST 15
  237:

COSTとは、符号長を表します。コストが小さい = 符号長が短い、となります。

コスト(COST)が小さくなるように、ハフマンテーブルをブロックに割り当てます。

  238: static
  239: void sendMTFValues ( EState* s )
  240: {

s->nblock [入力] 入力データブロック
s->inUse [入力] 入力データブロック中に存在するシンボルの生む
s->nInUse [入力] MTF変換前のシンボルの総数
s->mtfv [入力] MTF変換後
s->nMTF [入力] MTF変換後のデータ数
s->mtfFreq [入力] MTF変換後のシンボルの出現頻度

s->zlibts [出力] ハフマン符号化後のデータ
s->numZ [出力] ハフマン符号化後のデータバイト数

  241:    Int32 v, t, i, j, gs, ge, totc, bt, bc, iter;
  242:    Int32 nSelectors, alphaSize, minLen, maxLen, selCtr;
  243:    Int32 nGroups, nBytes;
  244:

  245:    /*--
  246:    UChar  len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
  247:    is a global since the decoder also needs it.
  248:
  249:    Int32  code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
  250:    Int32  rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
  251:    are also globals only used in this proc.
  252:    Made global to keep stack frame size small.
  253:    --*/
  254:
  255:

lenは、圧縮ファイルに書き出します。
code、rfreqは圧縮ファイルに書き出しません。

  256:    UInt16 cost[BZ_N_GROUPS];
  257:    Int32  fave[BZ_N_GROUPS];
  258:

cost[g] は、g番目のハフマンテーブルを使った場合の総コスト(符号長)。costが最小になるようなテーブルをブロックに割り当てます。今回の記事では使用しません。

fave[g] は、g番目のハフマンテーブルがブロックに共有された回数です。デバッグ出力用です。今回の記事では使用しません。

  259:    UInt16* mtfv = s->mtfv;
  260:

mtfvはMTF後のデータです。

  261:    if (s->verbosity >= 3)
  262:       VPrintf3( "      %d in block, %d after MTF & 1-2 coding, "
  263:                 "%d+2 syms in use\n",
  264:                 s->nblock, s->nMTF, s->nInUse );
  265:

s->nblokcは、入力ブロックデータ数。s->nMTFはMTF後のデータ数。
s->nInUseは入力ブロックのシンボル。
s->nInUse+2は、MTF時のシンボル数(ゼロランレングスによるシンボル1追加とEOB)。

  266:    alphaSize = s->nInUse+2;

alphaSizeはMTF後のシンボル数です。

  267:    for (t = 0; t < BZ_N_GROUPS; t++)
  268:       for (v = 0; v < alphaSize; v++)
  269:          s->len[t][v] = BZ_GREATER_ICOST;
  270:

s->lenは、ハフマン符号の符号長です。
s->len[t][v] は、t番目のハフマンテーブルのシンボルvの符号長を表します。

後に行う初期値セットの準備として、BZ_GREATER_ICOST をセットしています。

  271:    /*--- Decide how many coding tables to use ---*/
  272:    AssertH ( s->nMTF > 0, 3001 );
  273:    if (s->nMTF < 200)  nGroups = 2; else
  274:    if (s->nMTF < 600)  nGroups = 3; else
  275:    if (s->nMTF < 1200) nGroups = 4; else
  276:    if (s->nMTF < 2400) nGroups = 5; else
  277:                        nGroups = 6;
  278:

マルチプルハフマン符号で使用するテーブル数を決めます。
最大6個のハフマンテーブルを用いて、MTF後のデータを符号化します。

MTF後のデータサイズ s->nMTF に応じて、使用するハフマンテーブルの数を変えています。

  279:    /*--- Generate an initial set of coding tables ---*/

ハフマンテーブル(coding tables)の初期値を生成します。

各ハフマンテーブルに、セットする初期値の方針を紹介します。

シンボルを0〜6とします。またデータサイズ(出現頻度の合計)は900とします。
ハフマンテーブルは3つとします。

まず、データサイズ900をハフマンテーブルの数3で割ります。
900 / 3 = 300。
これは、各ハフマンテーブルが符号化したい(符号長を短くしたい)データ数(not シンボル数)を均等にするためです。
つまり、ハフマンテーブル0、1、2に、それぞれ300個程度のデータを符号化させたいです。

このために、シンボルを0から順に見ていって、出現頻度の合計が300程度になるシンボルを、各ハフマンテーブルに関連付けます。

上記の例では、シンボル0とシンボル1で出現頻度の合計が300になります。
シンボル2、シンボル3、シンボル4で出現頻度の合計が300になります。
シンボル5とシンボル6で出現頻度の合計が300になります。

以上より、ハフマンテーブル0に、シンボル0、シンボル1を関連付けます。

ハフマンテーブル1に、シンボル2、シンボル3、シンボル4を関連付けます。
ハフマンテーブル2に、シンボル5、シンボル6を関連付けます。

ハフマンテーブル0にシンボル0、シンボル1を関連付けるとは、シンボル0、シンボル1が多く含まれるブロックがハフマンテーブル0を共有した時に、コスト(符号長)が短くなるということです。

ここで注意するのは、これはあくまで初期値による割当であって、実際にこれでコストが最小になるわけではないという点です。

シンボル0とシンボル1を同じハフマンテーブル0で符号化しやすくしていますが、実際にはシンボル0とシンボル3とシンボル5を符号化しやすいハフマンテーブルの方がコストが小さくなるかもしれません。

このような場合に対応すべく、後のハフマンテーブルの割当改善でコストが小さくなるように改善していきます。

  280:    {
  281:       Int32 nPart, remF, tFreq, aFreq;
  282:
  283:       nPart = nGroups;
  284:       remF  = s->nMTF;
  285:       gs = 0;

nPartは初期化の終わっていないハフマンテーブルの数です。
nPart-1番目のハフマンテーブルに関連付けます。
(ハフマンテーブル番号の後ろから関連付けます)
remFは、関連付けていないデータ数です。
gsは、ハフマンテーブルに関連付ける開始シンボルです。
(gs〜geまでのシンボルをハフマンテーブルに関連付けます)

  286:       while (nPart > 0) {

1回のループで1つのハフマンテーブル(nPart番目のハフマンテーブル)にシンボルを関連付けます。

  287:          tFreq = remF / nPart;
  288:          ge = gs-1;
  289:          aFreq = 0;
  290:          while (aFreq < tFreq && ge < alphaSize-1) {
  291:             ge++;
  292:             aFreq += s->mtfFreq[ge];
  293:          }
  294:

tFreqは、データ数を未割当のハフマンテーブル数で割った値です。tFreqに相当する数のシンボルをハフマンテーブルnPartに関連付けます。
tFreqに相当する数のシンボルとは、シンボルi,j,kの出現頻度の合計がtFreqに近くなるようなシンボルです。

geはハフマンテーブルに関連付けます終端シンボルです(シンボルgs〜geを関連付けます)。
geの初期値をgs-1としています。
aFreqは、シンボルgs〜geの出現頻度の合計です。0で初期化します。

290行目のループで、シンボルgs〜geの出現頻度の合計aFreqがtFreqを超えない、かつge+1がシンボル内(<=alphaSize-1)に収まっている間、ge+1をハフマンテーブルに関連付けます。

291行目でgeをインクリメントして次のシンボルにします。
292行目で(291行目で更新した)シンボルgeの出現頻度s->mtfFreq[ge]をaFreqに加えています。

  295:          if (ge > gs
  296:              && nPart != nGroups && nPart != 1
  297:              && ((nGroups-nPart) % 2 == 1)) {
  298:             aFreq -= s->mtfFreq[ge];
  299:             ge--;
  300:          }
  301:

290行目の終了条件 aFreq < tFreq だと、常にaFreqがtFreqを超えてしまう。つまりハフマンテーブルに関連付けますシンボルが期待したい値(tFreq)を超えてしまいます。

この偏りを減らすために、295〜300行で、下記の条件時にハフマンテーブルに関連付けます最後のシンボルを一つ減らす(geを減らす)ようにします。

・ハフマンテーブルの番号が1でもnGroupsでもない(端でない)
・ハフマンテーブルの数が偶数の時は、テーブルの番号が奇数の時
　ハフマンテーブルの数が奇数の時は、テーブルの番号が偶数の時

図は、nGroupsが6の時、各ハフマンテーブルのaFreqがtFreqを超えるか超えないかを表しています。nPartが1、2、4、6の時、aFreqがtFreqを超えます。nPartが3、5の時、aFreqがtFreqを超えません。

  302:          if (s->verbosity >= 3)
  303:             VPrintf5( "      initial group %d, [%d .. %d], "
  304:                       "has %d syms (%4.1f%%)\n",
  305:                       nPart, gs, ge, aFreq,
  306:                       (100.0 * (float)aFreq) / (float)(s->nMTF) );
  307:

デバッグ出力です。
initial group 3, [0 .. 2], has 300 syms (30%)
出力が上記の場合、ハフマンテーブル3にシンボル0〜2を関連付け、シンボル0〜2はデータ中に300個含まれ、シンボル0〜2の全データ中での割合は30%、を意味します。

  308:          for (v = 0; v < alphaSize; v++)
  309:             if (v >= gs && v <= ge)
  310:                s->len[nPart-1][v] = BZ_LESSER_ICOST; else
  311:                s->len[nPart-1][v] = BZ_GREATER_ICOST;
  312:

今回割当対象のハフマンテーブルnPart-1 に対し、関連付けたいシンボルgs〜geに関してはコスト(符号長)をBZ_LESSER_ICOST (0)、それ以外のシンボルに関してはコストをBZ_GREATER_ICOST (15) にしています。

こうすることで、一回目のコスト算出時に、関連付けたシンボルを多く含むブロックで、このハフマンテーブルが使用されやすくなります。

  313:          nPart--;
  314:          gs = ge+1;
  315:          remF -= aFreq;

nPart--で、次のハフマンテーブルを更新
gs = ge+1で、次の関連付け開始シンボルを更新
remF -= aFreqで、残りデータ数を更新

  316:       }
  317:    }
  318:

まとめ

マルチプルハフマンテーブルの初期化方法を紹介しました。
次回は、符号長が短くなるようにマルチプルハフマンテーブルの割当を改善する方法を紹介します。