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

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

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

ブロックソーティングの実装（1）　変換

　それではブロックソーティングを実装しましょう。長くなるので区切りながら実装します。

　最初は変換の部分です。前回のコードの末尾の</body>の上に、以下のコードを挿入してください。

<script type="text/javascript">
String.prototype.toArray = function() {
  var ary = new Array(this.length);
  for (var i = 0; i < this.length; i++) {
    ary[i] = this.charAt(i);
  }
  return ary;
} 
 
var BWT_BLOCK_LEN = 1000;
function encodeBWT(data) {
  var encode_data = new Array();
  var BWT_BLOCK_LEN = data.length;
 
  var src_data = data;
  if ((data.length%BWT_BLOCK_LEN) != 0) {
    for (var i = 0; i < (BWT_BLOCK_LEN - (data.length%BWT_BLOCK_LEN)); i++) {
      src_data = src_data + '0';
    }
  }
  var block_num = src_data.length/BWT_BLOCK_LEN;
 
  encode_data.push(String.fromCharCode(data.length))
  encode_data.push(String.fromCharCode(block_num))
 
  for (var i = 0; i < block_num; i++) {
    var line = src_data.slice(i*BWT_BLOCK_LEN, (i+1)*BWT_BLOCK_LEN).toArray(); 
    var block = new Array();
 
    for (var j = 0; j < BWT_BLOCK_LEN; j++) {
      block.push(line.join("") + String.fromCharCode(j));
      var value = line.shift(i);
      line.push(value);
    }
 
    block.sort();
    var encode_line = new Array(BWT_BLOCK_LEN+1);
    for (var j = 0; j < BWT_BLOCK_LEN; j++) {
      var n = block[j].charAt(BWT_BLOCK_LEN);
      if (n == String.fromCharCode(0)) {
        encode_line[BWT_BLOCK_LEN] = String.fromCharCode(j);
      }
      encode_line[j] = block[j].charAt(BWT_BLOCK_LEN-1);
    }
    encode_data = encode_data.concat(encode_line);
  }
 
  return encode_data;
}
// 末尾1

2～8行目

文字列を配列に変換するメソッドです。組み込みのStringクラスにメソッドを追加しています。

10行目

ブロック長を定義しています。大きいデータ全体をブロックにしてしまうとブロックが巨大になります。文字列をある程度の長さで分けて、それぞれにブロックを作れるようにした方がパフォーマンスが良くなる可能性があります。ただし、今回は全部を1つのブロックとして処理しています。

11～49行目

ブロックソーティングの変換メソッドです。

13行目

上述のようにブロックの大きさを、変換するデータの長さに合わせています。

16～20行目

ブロックの大きさに合わない場合は、ダミーの文字列「0」で埋めるようにしています。

23行目

変換後のデータの先頭に、データの長さを文字に変換して入れています。