bzip2を読む ハフマン符号6

こんにちは、junkawaです。

本記事では、ハフマン符号化で使用した情報を出力バッファに書き出す前準備について紹介します。

  461:    /*--- Compute MTF values for the selectors. ---*/

s->selectorは、ブロックに割り当てたハフマンテーブル番号を保持しています。
これは圧縮ファイルに書き出す必要がある情報です。

ハフマンテーブル番号は0〜5なので1バイトに収まります。したがってs->selectorはUChar型の配列です。

s->selectorの最大サイズは約18,000バイトとなります。入力データブロックサイズ900,000をテーブル割当シンボル数50で割った値です。

s->selectorもそれなりのサイズになるので圧縮して書き出します。
圧縮の方法として、MTF変換後に521行目でUnary codingして圧縮します。

ここでは、s->selectorをMTF変換します。

  462:    {
  463:       UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
  464:       for (i = 0; i < nGroups; i++) pos[i] = i;

MTF変換用のリストposを初期化します。

  465:       for (i = 0; i < nSelectors; i++) {
  466:          ll_i = s->selector[i];
  467:          j = 0;
  468:          tmp = pos[j];
  469:          while ( ll_i != tmp ) {
  470:             j++;
  471:             tmp2 = tmp;
  472:             tmp = pos[j];
  473:             pos[j] = tmp2;
  474:          };
  475:          pos[0] = tmp;
  476:          s->selectorMtf[i] = j;
  477:       }
  478:    };
  479:

リストposの中からll_iを見つけ、その場所jをs->seletorMtfに保存します。
また、ll_iをpos[0]に移動します。(以前のpos[0]はpos[1]にずらしていきます)

  480:    /*--- Assign actual codes for the tables. --*/

今までは、ハフマンテーブルの符号長のみを扱ってきましたが、ここでシンボルに符号を割り当てます。

  481:    for (t = 0; t < nGroups; t++) {
  482:       minLen = 32;
  483:       maxLen = 0;
  484:       for (i = 0; i < alphaSize; i++) {
  485:          if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
  486:          if (s->len[t][i] < minLen) minLen = s->len[t][i];
  487:       }

ハフマンテーブルtの最小符号長minLen、最大符号長maxLenを求めています。
これらは、BZ2_hbAssignCodes()で無駄なループを回さないために用います。

  488:       AssertH ( !(maxLen > 17 /*20*/ ), 3004 );

maxLenが17ビット以下であることを確認します。

  489:       AssertH ( !(minLen < 1),  3005 );

minLenが1ビット以上であることを確認します。

  490:       BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]),
  491:                           minLen, maxLen, alphaSize );
  492:    }
  493:

BZ2_hbAssignCodes()でs->code[t]に符号を割り当てます。

まとめ

ハフマン符号化で使用した情報を出力バッファに書き出す前準備について紹介しました。