bzip2を読む ハフマン符号5
こんにちは、junkawaです。
本記事では、複数のハフマンテーブルを使って符号化を行うマルチプルハフマン符号化における、テーブル割当の改善方法についてソースコードを交えて紹介します。
当該関数は、sendMTFValues() @ compress.cです。
コードの紹介
sendMTFValues() @ compress.c
https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/compress.c#L239
bzlib_private.h
121: #define BZ_N_GROUPS 6
122: #define BZ_G_SIZE 50
123: #define BZ_N_ITERS 4BZ_N_GROUPSはハフマンテーブルの最大数。
BZ_G_SIZEは、ハフマンテーブルを割り当てるブロックのシンボル数。
BZ_N_ITERSは、ハフマンテーブルの改善回数。
319: /*---
320: Iterate up to BZ_N_ITERS times to improve the tables.
321: ---*/
322: for (iter = 0; iter < BZ_N_ITERS; iter++) {
323:BZ_N_ITERS (4) 回、ハフマンテーブルの割当を改善します。
324: for (t = 0; t < nGroups; t++) fave[t] = 0;
325:fave[t] はハフマンテーブルtがブロックに割り当てられた回数です。0で初期化します。
326: for (t = 0; t < nGroups; t++)
327: for (v = 0; v < alphaSize; v++)
328: s->rfreq[t][v] = 0;
329:割り当てたハフマンテーブルtにシンボルvが含まれる回数です。0で初期化します。
330: /*---
331: Set up an auxiliary length table which is used to fast-track
332: the common case (nGroups == 6).
333: ---*/通常、入力データブロック中のシンボルは約900,000になっています。ブロックソート、MTF変換、ランレングス符号化では、圧縮はほとんどなされません。
(ブロックソート、MTF変換ではシンボル数に変化はありません)
MTF変換後のシンボル数が2400以上の場合、nGroupsが6になります。
したがって、ほとんどの場合において、nGroupsは6となります。
334: if (nGroups == 6) {
335: for (v = 0; v < alphaSize; v++) {
336: s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v];
337: s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v];
338: s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v];
339: }
340: }
341:nGroupsが6の時、複数のコスト計算を1回の計算にまとめて高速化するために、s->lenの代わりにs->len_packを使用します。
s->len_pack[v][0] は、ハフマンテーブル0とハフマンテーブル1のシンボルvの符号長を収めています。上位2バイト(16ビット)にハフマンテーブル1のシンボルvの符号長、下位2バイトにハフマンテーブル0のシンボルvの符号長が入っています。
同様に、s->len_pack[v][1] は、ハフマンテーブル2とハフマンテーブル3のシンボルvの符号長、s->len_pack[v][2] は、ハフマンテーブル4とハフマンテーブル5のシンボルvの符号長が入っています。
342: nSelectors = 0;
343: totc = 0;
344: gs = 0;nSelectors は、MTF後のデータをBZ_G_SIZEシンボル毎に区切ったブロックの番号です。0で初期化します。
totcは、total costで、今回のハフマンテーブル割当の結果の総コストを表します。
ここでいうコストとは、前回のループで決定したハフマンテーブルを用いて計算した結果の符号長の合計値です。
デバッグ出力用です。
gsはMTF後のデータのブロックの先頭シンボル番号です。
345: while (True) {
346:全ブロックにハフマンを割り当てるまでループを回します。
347: /*--- Set group start & end marks. --*/
348: if (gs >= s->nMTF) break;gsがMTF後データのシンボル数(s->nMTF)を超えた場合、割当が完了したとして、ループを抜けます。
349: ge = gs + BZ_G_SIZE - 1;
350: if (ge >= s->nMTF) ge = s->nMTF-1;
351:今回のループでは、s->mtfv[gs]〜s->mtfv[ge]に、一つのハフマンテーブルを割り当てます。
350行目で、geがMTF後のシンボル数を超えた場合、最後のデータとなるs->nMTF-1としています。
352: /*--
353: Calculate the cost of this group as coded
354: by each of the coding tables.
355: --*/各ハフマンテーブルによって符号化化されたこのグループのコストを計算します。
356: for (t = 0; t < nGroups; t++) cost[t] = 0;
357:costを0で初期化します。
358: if (nGroups == 6 && 50 == ge-gs+1) {
359: /*--- fast track the common case ---*/nGroupsが6で、ブロックのシンボル数が50の時、処理を高速化できます。
50というマジックナンバーになっていますが、BZ_G_SIZEのことだと思われます。
360: register UInt32 cost01, cost23, cost45;
361: register UInt16 icv;
362: cost01 = cost23 = cost45 = 0;
363:cost01は、ハフマンテーブル0を割り当てた場合の符号長の合計と、ハフマンテーブル1を使った場合の符号長の合計が入っています。
364: # define BZ_ITER(nn) \
365: icv = mtfv[gs+(nn)]; \
366: cost01 += s->len_pack[icv][0]; \
367: cost23 += s->len_pack[icv][1]; \
368: cost45 += s->len_pack[icv][2]; \
369:icvは、MTF後データのgs+nn番目のシンボルです。
s->len_pack[icv][0]の上位2バイトにはハフマンテーブル1を使った(割り当てた)場合のicvの符号長が入っています。下位2バイトにはハフマンテーブル0を使った(割り当てた)場合のicvの符号長が入っています。
したがって、cost01 には、ハフマンテーブル0とハフマンテーブル1を使った場合の符号長の合計が入ります。
同様に、cost23にはハフマンテーブル2とハフマンテーブル3を使った場合の符号長の合計、cost45にはハフマンテーブル4とハフマンテーブル5を使った場合の符号長の合計が入ります。
備考
50シンボルで、1シンボルの最大長は17ビットです。各テーブルの符号長の合計の最大値は50*17で850となります。これは1バイト(最大255)には収まらない値なので2バイト必要です。したがって、テーブルの符号長をまとめる時に、上位2バイトと下位2バイトを使用しています。
370: BZ_ITER(0); BZ_ITER(1); BZ_ITER(2); BZ_ITER(3); BZ_ITER(4);
371: BZ_ITER(5); BZ_ITER(6); BZ_ITER(7); BZ_ITER(8); BZ_ITER(9);
372: BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14);
373: BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19);
374: BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24);
375: BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29);
376: BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34);
377: BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39);
378: BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44);
379: BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49);
380:BZ_ITER(0)〜BZ_ITER(49)を実行することで、gs〜geにハフマンテーブル0〜5を割り当てた場合の符号長の合計がcost01、cost23、cost45に入ります。
381: # undef BZ_ITER
382:BZ_ITERをundefします。
383: cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16;
384: cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16;
385: cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16;
386:2つのテーブルのコスト計算を1回にまとめていたので、結果を分離します。
cost01の下位2バイトをハフマンテーブル0のコストcost[0]にセットします。
cost01の上位2バイトをハフマンテーブル1のコストcost[1]にセットします。
同様に、cost23、cost45をcost[2]、cost[3]、cost[4]、cost[5]にセットします。
387: } else {
388: /*--- slow version which correctly handles all situations ---*/nGroupsが6ではないか、ブロックのシンボル数が50ではない時、このブロックを実行します。
389: for (i = gs; i <= ge; i++) {
390: UInt16 icv = mtfv[i];
391: for (t = 0; t < nGroups; t++) cost[t] += s->len[t][icv];
392: }cost[t]に、ハフマンテーブルtの符号icvの符号長s->len[t][icv] を加算しています。
高速化版とは異なり、ハフマンテーブル1個ずつでコストを計算しています。
393: }
394:ここまでで、cost[0]〜cost[5]が計算されました。
395: /*--
396: Find the coding table which is best for this group,
397: and record its identity in the selector table.
398: --*/
399: bc = 999999999; bt = -1;
400: for (t = 0; t < nGroups; t++)
401: if (cost[t] < bc) { bc = cost[t]; bt = t; };ハフマンテーブル0〜nGroups-1の中で、このブロックに割当てた時に一番コストが小さくなるものを探します。
コストが一番小さくなるハフマンテーブルの番号をbtに、その時のコストをbcに保存します。
402: totc += bc;
403: fave[bt]++;
404: s->selector[nSelectors] = bt;
405: nSelectors++;
406:コストbcをトータルコストtotcに加算します。
ハフマンテーブルbtの割当回数fave[bt]をインクリメントします。
本ブロックに割り当てたテーブルを記録するセレクタs->selector[nSelectors]にハフマンテーブル番号btを記録します。
次のブロックのためにnSelectorsをインクリメントします。
407: /*--
408: Increment the symbol frequencies for the selected table.
409: --*/コストが最小となったハフマンテーブルbt用に、ブロックに含まれるシンボルの出現頻度をカウントします。
410: if (nGroups == 6 && 50 == ge-gs+1) {
411: /*--- fast track the common case ---*/
412:ハフマンテーブル数が6で、ブロック中のシンボル数が50の時、高速化の処理を行います。
413: # define BZ_ITUR(nn) s->rfreq[bt][ mtfv[gs+(nn)] ]++
414:
415: BZ_ITUR(0); BZ_ITUR(1); BZ_ITUR(2); BZ_ITUR(3); BZ_ITUR(4);
416: BZ_ITUR(5); BZ_ITUR(6); BZ_ITUR(7); BZ_ITUR(8); BZ_ITUR(9);
417: BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14);
418: BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19);
419: BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24);
420: BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29);
421: BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34);
422: BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39);
423: BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44);
424: BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49);
425:430行目のforループを展開(Loop Unrolling)したものです。
forループに比べ、ループの終了条件を行う必要がないため、その分高速化できます。
gs+0〜ge+49まで50回、実行します。
426: # undef BZ_ITUR
427:BZ_ITURをundefします。
428: } else {
429: /*--- slow version which correctly handles all situations ---*/ハフマンテーブル数が6ではない、もしくはブロック中のシンボル数が50でない場合、実行されます。
430: for (i = gs; i <= ge; i++)
431: s->rfreq[bt][ mtfv[i] ]++;ブロックに含まれるシンボル(mtfv[gs]〜mtfv[ge])の出現頻度をs->freq[bt]に記録します。
btは、このブロックに対してコスト(符号長)が最も小さかったハフマンテーブルの番号です。
(ハフマンテーブルの内容は、前回のループで決まった内容です。)
432: }
433:
434: gs = ge+1;次のブロックにハフマンテーブルを割り当てるために、次のブロックの開始番号gsを、今回のブロックの終端番号geに1を足したもので更新します。
435: }345行目のループがここで完了し、全てのブロックについてハフマンテーブルの割当が完了しました。
436: if (s->verbosity >= 3) {
437: VPrintf2 ( " pass %d: size is %d, grp uses are ",
438: iter+1, totc/8 );
439: for (t = 0; t < nGroups; t++)
440: VPrintf1 ( "%d ", fave[t] );
441: VPrintf0 ( "\n" );
442: }
443:デバッグ出力です。
iter+1は何回目の改善なのか、totc/8は、前回のハフマンテーブルを使って割り当てた場合の符号長のバイト数(totcがビットなので8で割ってバイトにしています)。
fave[t]は、ハフマンテーブルtが割り当てられた回数です。
444: /*--
445: Recompute the tables based on the accumulated frequencies.
446: --*/今回の割当で計算した出現頻度を元にハフマンテーブルの符号長を再計算します。
447: /* maxLen was changed from 20 to 17 in bzip2-1.0.3. See
448: comment in huffman.c for details. */符号長の最大値は1.0.3以降、17ビットになりました。それ以前は20ビットでした。
449: for (t = 0; t < nGroups; t++)
450: BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]),
451: alphaSize, 17 /*20*/ );
452: }
453:
454:今回のループでハフマンテーブルに関連付けられたブロック内の符号の出現頻度s->rfreqをもとに、各ハフマンテーブルの符号長を再計算します。
割当時には、前回のループで決まったハフマンテーブルを使っています。
今回の割当は、前回のハフマンテーブルの符号長で最適な割当です。それをもとにハフマンテーブルの符号長を再計算しているため、前回よりも符号長が短くなることが期待できます。
455: AssertH( nGroups < 8, 3002 );519行目でnGroupsを3ビットで、圧縮ファイルに書き出しています。
そのため、nGroupsが3ビット(0〜7)に収まるかを確認しています。
456: AssertH( nSelectors < 32768 &&
457: nSelectors <= (2 + (900000 / BZ_G_SIZE)),
458: 3003 );
459:
460:nSelectors の最大値は、単純化すると、入力データブロック900,000 シンボルにMTF変換によるゼロランレングス1、EOBの2シンボルが追加された900,002シンボルをBZ_G_SIZEで割った値となります。
また、520行目でnSelectorsを15ビットで、圧縮ファイルに書き出しています。
そのため、nSelectorsが15ビット(0〜32767)に収まるかを確認しています。
まとめ
マルチプルハフマン符号化における、テーブル割当の改善方法について紹介しました。
ご覧下さりありがとうございます。いただいたサポートは図書館への交通費などに使わせていただきます。