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

» 2009年03月04日 00時00分公開

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

ハフマン符号の実装―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[文字コード] ＝出現回数

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