プロダクションエンジニア平成１２年午後１問２

末広ページへ　このコーナーの目次へ

問２　ファイルの圧縮に関する次の記述を読んで，設問1〜4に答えよ。

　図１はあるファイルのバイト列の一部である。今この内容を圧縮することを考える。なお，バイト列はすべて 16 進数で表され１バイトは 8  ビットである。

（1）　圧縮形式の検討

　バイトの並び方に着目すると，0 〜 3 バイト目と 5 〜 8 バイト目は同じ内容の繰返しになっている。このような場合，2 回目に出現するバイト列は，同じバイト列が存在するファイル内の位置情報（ 0 バイト目）と長さ情報（ 4 バイト分）で置き換え、（00．04）と表現することによって．ファイルの内容を圧縮できる（図2）。

　圧縮したバイト列を表す位置情報と長さ情報の組を圧縮データ，それ以外の各バイトを非圧縮デ−夕と呼ぶ。圧縮データと非圧縮データを単に並べたのでは，圧縮されたファイルの中で圧縮データと非圧縮データの判別ができなくなってしまう。そこで，8個のデータごとに1バイトのデータ判別フラグを挿入することにする。データ判別フラグは，2進数表現した8ビットを最上位ビットから最下位ビットに向かって，その直後に続＜．8個のデータと対応させ，各ビットが0であれば圧縮データを，1であれば非圧縮データを表すことにする（図3）。

図３　データ判別フラグと圧縮データ/非圧縮データの対応

　なお，ファイル終端部においてデ−タ判別フラグのビットに対応するデータが存在しない場合，そのビットは参照されないので，どのような値であっても構わないが，ここでは 0 とする。

　圧縮データは効率を考慮して 2 バイトの形式とし，次のとおり定義する。

　圧縮データの1バイト日をCl，2バイト目をC2としたとき，Cl，C2と位置情報，長さ情報の関係を，次の計算式で表す。

　位置情報＝（C2の上位4ビット）×256＋C1

　長さ情報＝（C2の下位4ビット）＋3

　つまり，圧縮データ 2 バイトのうち，位置情報に 12 ビット，長さ情報に 4 ビットを使用する。ここで，圧縮前ファイルの大きさは 4,095 バイト以下とし，また，3バイト以上が一致するバイト列だけを圧縮の対象とするので，C2 の下位 4 ビットは，実際に一致するバイト列の長さから 3 引いた値とする。

　なお，圧縮デ−夕は圧縮前ファイルに対する位置情報と長さ情報から作成する。圧縮した結果は，圧縮後ファイルに出力し，圧縮データを含むバイト列を更に圧縮することはない。この圧縮形式によって図１に示すバイト列を圧縮した結果は，図４のとおりとなる。

（2）庄縮アルゴリズムの検討

　主要なアルゴリズムは，あるバイトの並びに対してファイル内のその位置より前で，最も良く一致するバイト列を検索することである。今回，検索には2分木を利用したアルゴリズムを採用する。

　ファイルの内容をすべて読み込んだ 1 次元配列 Buffer (先頭の添字は0）の要素を先頭から順次走査し，同じ値で始まるバイト列をノ−ドとする 2 分木を作成する。例えば，図１に示したバイト列の中で，"41" という値だけに着目した場合，初めて "41" が出現する添字 0 で始まるバイト列を木の根とする。次に "41" が出現する添字 5 で始まるバイト列を木に追加する。このとき，既に木に存在するバイト列とこれから木に追加するバイト列を 1 バイトずつ順次比較し，追加するバイト列の要素の方が小さければ左ノードとして，大きければ右ノードとして追加する。添字 5 で始まるバイト列は，添字 0 で始まるバイ卜列よりも小さいので，根の左ノードとして木へ追加する。

図５　図１における値 "41" の２分木

　アルゴリズムでは，添字 j で始まるバイト列を木に追加する処理と同時に，木に含まれるバイト列の中で，添字 i で始まるバイト列と最も長く一致するノードの添字と長さを求めていく。2 分木を利用した検索では，添字 i で始まるバイト列と，あるノ−ドのバイト列との比較で，添字 i で始まるバイト列の方が小さければ左ノードを，大きければ右ノードを順次たどればよく，検索回数を減らすことが可能となる。

　次に示すのは，木にノードを追加する部分のアルゴリズム及び主なデータ域である。このアルゴリズムは，圧縮のメインのアルゴリズムから呼び出され，これから木に追加するバイト列の先頭の添字 Index を引数として受け取り，MatchPos 及び MatchLen に適切な値を設定して終了する。

　　なお，メインのアルゴリズムは，Index を 0 から順に一つずつ増加させながら配列の終わりまでこのアルゴリズムを呼び出し，MatchLen が 3 以上であれば，MatchPos 及び MatchLen から圧縮データを作成する。

〔木にノードを追加ずるアルゴリズム〕
(斎藤注：空欄が分かりにくいため赤で強調）

 AddTree(Index){
   MatchLen ← O; MatchPoS ← NULL;
 「　　　　ａ　　　」
  Left[Index] ← NULL; Right[Index] ← NULL;
  if(SearchIndex = NULL){
      Root[Buffer[Index]] ← Index; return
   )
   while(TRUE){
      i ← 1;
     while(i < MAXLEN){
        if ( Index+i ≧ FileLen){
           Dif ← 0;
            exit
      }else{
         Dif ← 「　  ｂ  　」;
         if(Dif≠0){exit}
         i ← i+1
      }
     }
     if(i > HitchLen){
       MatchPos ← Searchlndex; MatchLen ← i
     }
     if(Dif>0){
       if(Right[Searchlndex]= NULL) {
          Right[Searchlndexl ← Index; return
        }else{
           Searchlndex ← Right[Searchlndex],
        }
      }else{
        if(Left[Searchlndex] = NULL) {
           Left[Searchlndexl ← Index; return
        }else{
           Searchlndex ← Left [Searchlndex]
         }
      }
    }
 }

設問１

　次の14バイトのバイト列（16進数）を，本圧縮形式で圧縮したバイト列に変換し，解答欄に記入せよ。

　なお，解答はすべて16進数で記入し，余った枠は空白とすること。

設問２

　アルゴリズム中の[ a ], [ b ] に入れる適切な文又は式を答えよ。

設問３

　アルゴリズム中で使用される MAXLEN として設定可能な最大値は幾つか。10 進数で答えよ。

設問４

　設問1のバイト列を圧縮し終わった状態での各配列 Root，Left，Right について，次の図を完成させよ。

　なお，解答は10進数又は NULL を記入すること。

末広ページ　このコーナの目次

spage@yscon.co.jp