データ量を操る圧縮／展開を究めよう：コーディングに役立つ！ アルゴリズムの基本（8）（4/5 ページ）

プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか（編集部）

[山下寛人，オイシックス株式会社]

ハフマン符号の実装―1

　それでは実装していきましょう。長くなるのでいくつかに分割しながら解説します。

　先ほどのコードの29行目、「末尾2」のコメントの下の行に以下のコードを追加してください。

<script type="text/javascript">
Array.prototype.clone = function(){
  return this.slice(0);
}
 
function HuffmanTree(data, is_compressed_data) {
  if (is_compressed_data) {
    this.setCompressedData(data);
  } else {
    this.data = data;
    var char_counter = this.getCharCounter();
    this.setHeaderData(char_counter);
    this.setTreeData();
  }
}
 
HuffmanTree.prototype.getCharCounter = function() {
  var char_counter = new Array();
  for (var i = 0; i < this.data.length; i++) {
    var ch_num = this.data.charCodeAt(i);
    if (char_counter[ch_num] == undefined) {
      char_counter[ch_num] = 0;
    }
    char_counter[ch_num]++;
  }
 
  return char_counter;
}
<!-- 末尾3 -->

　コードを解説していきます。

2〜4行目

汎用メソッドです。配列のコピーを行うメソッドです。

6〜15行目

ハフマン符号の木構造を表すクラスです。圧縮機能も持ちます。コンストラクタに渡されたデータが圧縮していないものであれば圧縮し、圧縮したものであれば復元します。

8行目

圧縮されたデータを受け取った場合は復元します。

11行目

文字ごとの出現回数をカウントした表を作ります。データ構造は文字コードをキーとする配列になっています。

12行目

出現回数の表を、文字コード（ch_num）と出現回数（count）の組み合わせのデータに変換し、ヘッダデータとして保持します。

13行目

木構造を作成します。

17〜28行目

文字ごとの出現回数をカウントするメソッドです。

ハフマン符号の実装―2

　引き続き実装していきます。次のコードは上のコードの続きです。29行目「末尾3」の下に続きます。

HuffmanTree.prototype.setHeaderData = function(char_counter) {
  this.header_data = new Array();
 
  for (var ch_num = 0; ch_num < char_counter.length; ch_num++) {
    if (char_counter[ch_num] === undefined) { continue; }
    var ch_count_data = { count:char_counter[ch_num], ch_num:ch_num };
    this.header_data.push(ch_count_data);
  }
}
 
Array.prototype.insert_count = function(value) {
  for (var i = this.length-1; 0 <= i; i--) {
    if (value.count < this[i].count) { break; }
    this[i+1] = this[i];
  }
  this[i+1] = value;
}
 
HuffmanTree.prototype.setTreeData = function() {
  var sort_data = this.header_data.clone();
  sort_data.sort(function(a,b) { return b.count - a.count; });
 
  while(true) {
    var min1 = sort_data.pop();
    var min2 = sort_data.pop();
    if(min2 === undefined) {
      this.tree_data = min1;
      break;
    }
 
    var count = min1.count + min2.count;
    var node = { count: count, left: min1, right: min2 };
    sort_data.insert_count(node);
  }
}
<!-- 末尾4 -->

1〜9行目

getCharCounter()で、作られたデータは文字コードをキーとする配列になっています。

char_counter[文字コード] ＝出現回数

これを文字コードと出現回数を持つオブジェクトに変換します。後で木構造を作るときに使うためです。

11〜17行目

出現回数の配列にオブジェクトを追加するメソッドです。出現回数が多い順にソートされている状態のときに、多い順が保たれるように追加します。

19〜35行目

木構造を作成します。

20、21行目

ヘッダデータをコピーしてソートします。多い順にソートします。

23行目

ループを開始します。

24、25行目

配列からデータを取り出します。popは末尾からデータを取得して配列から削除するので、min1には一番出現回数が少ないもの、min2にはその次に出現回数が少ないものが入ります。

26〜29行目

ループの終わりですが、後で解説します。

31、32行目

出現回数を足して、木構造のノードを作成します。ノードは左側（left）が出現回数が少なく、右側（right）が出現回数が多いものになります。

33行目

sort_dataにノードを追加します。

　setTreeDataのループでは、配列からデータを取得してノードを作成し、それを元の配列に入れていきます。そのため、ループ2週目以降は配列の中に文字のデータと木構造の両方が入り、徐々に木構造に追加されていく形になっています。

　最終的には、木構造が1つだけ入った形になります。こうなったら木構造をインスタンス変数として保持し、ループを終了します。