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

プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか（編集部）

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

ブロックソーティングの実装（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行目

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

25行目

変換後のデータの先頭に、ブロック数を文字に変換して入れています。

26行目

ブロックごとのループです。

27行目

データから1ブロック分を切り出します。

30〜34行目

1文字ずつローテーションしてブロックを作っていきます。

31行目

ブロックの各行の末尾に、何回ローテーションしたときの文字列かという情報を文字に変換して追加しています。元の文字列が何行目だったかを後で判別するためです。

36行目

ブロックをソートします。blockは1つの要素がブロックの1行になっています。単純にソートするとブロックの左端の文字を基準にソートされます。

38〜46行目

ブロックの一番右の文字を順に取り出していきます。

40〜42行目

いま、ループで注目している行が元の文字列だった場合、その行数を変換後の文字列の末尾に文字に変換して追加します。

45行目

変換後のデータを作成しています。

　データ変換の過程のイメージを図示します。