データを加工して圧縮率を高めよう：コーディングに役立つ！ アルゴリズムの基本（9）（5/5 ページ）

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

MTFの実装

　それではMTFを実装しましょう。

　先ほどのソースコードの「//末尾3」のコメントの下に以下のコードを追加してください。

<script type="text/javascript">
Array.prototype.index_of = function(value) {
  for(var i = 0; i < this.length; i++) {
    if (this[i] == value) { return i; }
  }
 
  return -1;
}
 
Array.prototype.remove = function(index) {
  for (var j = index; j < this.length-1; j++) {
    this[j] = this[j+1];
  }
  this.pop();
}
 
function encodeMTF(data) {
  var encode_data = new Array();
  var ch_list = new Array();
 
  for (var i = 0; i < data.length; i++) {
    var ch = data.charAt(i);
    var index = ch_list.index_of(ch);
    if (index == -1) { ch_list.push(ch); }
  }
 
  encode_data[0] = String.fromCharCode(ch_list.length);
  encode_data = encode_data.concat(ch_list);
 
  for (var i = 0; i < data.length; i++) {
    var ch = data.charAt(i);
    var index = ch_list.index_of(ch);
    if (index == -1) { alert(ch_list); }
    ch_list.remove(index);
    ch_list.unshift(ch);
    encode_data.push(String.fromCharCode(index));
  }
 
  return encode_data;
}
 
function decodeMTF(data) {
  var decode_data = new Array();
 
  var len = data[0].charCodeAt(0);
  var ch_list = data.slice(1, len+1);
 
  for (var i = len+1; i < data.length; i++) {
    var index = data[i].charCodeAt(0);
    var ch = ch_list[index];
    ch_list.remove(index);
    ch_list.unshift(ch);
    decode_data.push(ch);
  }
 
  return decode_data;
} 
// 末尾4

2〜8行目

配列の中である値が何番目にあるかを調べる汎用的なメソッドです。組み込みの配列にメソッドを追加しています。

10〜15行目

配列の中の1要素を削除する汎用的なメソッドです。同じく組み込みの配列にメソッドを追加しています。

17〜43行目

MTFの変換をする関数です。

21〜25行目

文字リストを作成しています。

27〜28行目

変換後の文字列の最初の部分に文字リストの長さと文字リストを入れています。

31〜37行目

1文字ずつループしています。

31〜32行目

1文字取り出して文字リスト中の何番目か調べます。

34〜35行目

文字リストの中の文字を取り出して先頭に移動します。

36行目

変換後のデータに追加します。解説では数字で解説しましたが、実装では数値から文字コードに変換しているので注意してください。

42〜57行目

MTFの復元をする関数です。

45〜46行目

文字列リストを取り出しています。

48〜54行目

1文字ずつループします。

49〜50行目

1文字取り出し、文字リストの中から該当する文字を取り出します。

51〜52行目

文字リストの中で該当する文字を先頭に移動します。

53行目

復元した文字列に文字を追加していきます。

ブロックソーティング＋MTF＋ハフマン符号

　では、ブロックソーティングとMTFとハフマン符号を組み合わせて圧縮してみましょう。

　先ほどのコード「//末尾4」のコメントの後に以下のコードを追加してください。

function execMTF(input, output) {
  var data = getStringById(input);
  var element = document.getElementById(output);
  element.innerHTML = "元のデータ量: " + data.length + "<br>";
 
  var encode_data = encodeMTF(data);
  if (encode_data == null) { return; }
 
  element.innerHTML += "変換しました。<br>";
  element.innerHTML += "変換後のデータ量: " + encode_data.length + "<br>";
  element.innerHTML += "データを復元します。<br>";
 
  var decode_data = decodeMTF(encode_data);
  if (decode_data == null) { return; }
 
element.innerHTML += decode_data.join("");
}
</script>
<br/>
<input type="button" onClick="execMTF('area1','area2');" value="MTF">
<script type="text/javascript">
function execBWT_MTF_Huffman(input, output) {
  var data = getStringById(input);
  var element = document.getElementById(output);
  element.innerHTML = "元のデータ量: " + data.length + "<br>";
 
  var encode_bwt_data = encodeBWT(data);
  if (encode_bwt_data == null) { return; }
 
  var encode_mtf_data = encodeMTF(encode_bwt_data.join(""));
  if (encode_mtf_data == null) { return; }
 
  var encode_huffman_data = encodeHuffman(encode_mtf_data.join(""));
  if (encode_huffman_data == null) { return; }
 
  element.innerHTML += "圧縮しました。<br>";
  element.innerHTML += "圧縮後のデータ量: " + encode_huffman_data.byte_size() + "<br>";
  element.innerHTML += "データを復元します。<br>";
 
  var decode_huffman_data = decodeHuffman(encode_huffman_data);
  if (decode_huffman_data == null) { return; }
 
  var decode_mtf_data = decodeMTF(decode_huffman_data);
  if (decode_mtf_data == null) { return; }
 
  var decode_bwt_data = decodeBWT(decode_mtf_data);
  if (decode_bwt_data == null) { return; }
 
  element.innerHTML += decode_bwt_data.join("");
  element.innerHTML += "<br/>圧縮率: ";
  element.innerHTML += parseInt(encode_huffman_data.byte_size() / data.length * 100);
  element.innerHTML += "%<br/>";
}
</script>
<br/>
<input type="button" onClick="execBWT_MTF_Huffman('area1','area2');" value="BWT_MTF+Huffman">

　動作確認のためMTFだけの実行ボタンもあります。「BWT_MTF+Huffman」と書いてあるボタンをクリックしてください。

　ハフマン符号では圧縮率は65〜66％だったものが、62〜63％とより圧縮できました。以上で圧縮アルゴリズムの紹介を終わります。

著者紹介

山下 寛人

オイシックス株式会社

「次回」へ

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

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