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

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

ハフマン符号の実装―3

　引き続き実装します。次は、最終的な圧縮データを作る部分です。先のコード36行目「末尾4」の下に以下のコードを追加します。

HuffmanTree.prototype.getEncodeData = function() {
  var encode_data = new BitArray();
 
  encode_data.add(this.header_data.length, 8);
  for (var i = 0; i < this.header_data.length; i++) {
    var ch_count_data = this.header_data[i];
    encode_data.add(ch_count_data.ch_num, 16);
    encode_data.add(ch_count_data.count, 16);
  }
 
  var ch_map = new Array();
  function make_ch_map(node, code, len) {
    if (node.ch_num !== undefined) {
      ch_map[node.ch_num] = { code: code, len: len };
    } else {
      make_ch_map(node.left, (code << 1) + 1, len+1);
      make_ch_map(node.right, (code << 1), len+1);
    }
  }
  make_ch_map(this.tree_data, 0, 0);
 
  for (var i = 0; i < this.data.length; i++) {
    var huffman_code =ch_map[this.data.charCodeAt(i)];
    encode_data.add(huffman_code.code, huffman_code.len);
  }
 
  return encode_data;
}
<!-- 末尾5 -->

2行目

圧縮後データをBitArrayオブジェクトとして、インスタンスを作成します。

3行目

今回の実装では、先頭にヘッダデータの長さを保持します。ヘッダデータの長さを8ビット分のデータとしてencode_dataに追加します。

5〜9行目

ヘッダデータ（各文字とその出現回数）をencode_dataに追加していきます。1文字に16ビット、出現回数にも16ビット使います。

11行目

ch_mapは文字ごとの変換後の2進数データを保持する配列です。

12〜20行目

ツリーをたどりながら各文字の変換後の2進数データを作っていきます。ここでは、再帰を使っています。

ビットデータの作成のところで解説したとおりの動作になっています。ビットシフトもあり、やや難しいかもしれませんが、よくコードを読んで動作を想像してみてください。

22〜25行目

圧縮前データの各文字に対して変換後のビットデータを取得し、順次encode_dataに追加していきます。これですべての圧縮処理は終了です。

ハフマン符号の実装―4

　最後は復元です。もう少しで終わりなので頑張りましょう。先のコード「末尾5」の下に以下のコードを追加してください。

HuffmanTree.prototype.setCompressedData = function(data) {
 
  var len = data.get(0,8);
  var char_counter = new Array();
  for (var i = 0; i < len; i++) {
    var ch_num = data.get(8+(i*32), 16);
    var count = data.get(24+(i*32), 16);
    char_counter[ch_num] = count;
  }
 
  this.setHeaderData(char_counter);
  this.setTreeData();
 
  var decode_data = new Array();
 
  function rec(arg_node, i) {
    var node = arg_node;
    if (node.ch_num !== undefined) {
      var ch = String.fromCharCode(node.ch_num);
      decode_data.push(ch);
      return i;
    }
 
  var bit = data.get(i,1);
  if (bit === null) { return; }
 
  if (bit == 0) {
    return rec(node.right, i+1);
  } else {
    return rec(node.left, i+1);
  }
}
 
  var index = 8 + (len*32);
  while(index < data.length) {
    index = rec(this.tree_data, index);
  }
 
  this.data = decode_data;
}
<!-- 末尾6 -->

3行目

先頭の8ビットを、ヘッダの長さデータとして取得します。

5〜9行目

ヘッダデータの長さ分ループし、文字コードと出現回数をビット列から取得していきます。

11行目

ヘッダデータをオブジェクトの配列に変換します。

12行目

木構造を作成します。

16〜32行目

1文字復元する関数です。ビット列を1ビットずつ取得し、1か0によって左のノードか右のノードに移動します。ノードが文字のノードだったらその文字をdecode_dataに追加し、そうでなければさらに左右のノードに移動していきます。最終的には必ず文字のノードに突き当たります。

34行目

実データの先頭のビットの位置を計算しています。

35〜37行目

ビット列を順に追ってデータを復元していきます。

39行目

すべて復元できたらインスタンス変数に保持します。

ハフマン符号の圧縮率

　最後に、実行部分をコードに追加します。先のコード41行目、「末尾6」の次に以下のコードを追加します。

HuffmanTree.prototype.getDecodeData = function() {
  return this.data;
}
 
function encodeHuffman(data) {
 
  var huffmanTree = new HuffmanTree(data, false);
  var encode_data = huffmanTree.getEncodeData();
 
  return encode_data;
}
 
function decodeHuffman(data) {
 
  var huffmanTree = new HuffmanTree(data, true);
  var decode_data = huffmanTree.getDecodeData();
 
  return decode_data;
} 
 
function execHuffman(input, output) {
  var data = getStringById(input);
  var element = document.getElementById(output);
  element.innerHTML = "元のデータ量: " + data.length + "<br>";
 
  var encode_data = encodeHuffman(data);
  if (encode_data == null) { return; }
  element.innerHTML += "圧縮しました。<br>";
  element.innerHTML += "圧縮後のデータ量: " + encode_data.byte_size() + "<br>";
  element.innerHTML += "データを復元します。<br>";
 
  var decode_data = decodeHuffman(encode_data);
  if (decode_data == null) { return; }
 
  element.innerHTML += decode_data.join("");
  element.innerHTML += "<br/>圧縮率: ";
  element.innerHTML += parseInt(encode_data.byte_size() / data.length * 100);
  element.innerHTML += "%<br/>";
}
</script>
<input type="button" onClick="execHuffman('area1','area2');" value="Huffman">

　Webブラウザで実行してみましょう。「Huffman」というボタンをクリックすると、気になる圧縮率は……。65％や66％という結果が出たと思います。見事に圧縮されました。

　次回はさらに工夫してより圧縮率を上げていきたいと思います。

著者紹介

山下 寛人

オイシックス株式会社

「次回」へ

「コーディングに役立つ！ アルゴリズムの基本」バックナンバー

• レコメンデーションとエディットグラフ
• データを加工して圧縮率を高めよう
• データ量を操る圧縮／展開を究めよう
• 文字列の中から効率良くキーワードを探し出せ
• Firebugで探索アルゴリズムを見ていこう
• Internet Explorerよりも速くソートできたよ
• Internet Explorerよりも速くソートできるかな
• 再帰でハノイの塔を攻略せよ
• データ構造の選択次第で天国と地獄の差
• いまさらアルゴリズムを学ぶ意味