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

» 2009年04月02日 00時00分 公開
[山下寛人オイシックス株式会社]
前のページへ 1|2|3|4|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%とより圧縮できました。以上で圧縮アルゴリズムの紹介を終わります。

著者紹介

山下 寛人

オイシックス株式会社



前のページへ 1|2|3|4|5       

Copyright © ITmedia, Inc. All Rights Reserved.

RSSについて

アイティメディアIDについて

メールマガジン登録

@ITのメールマガジンは、 もちろん、すべて無料です。ぜひメールマガジンをご購読ください。