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

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

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

ブロックソーティングの実装（2）　復元

　復元部分の実装を進めます。

　先のソースコード「//末尾1」の下の行に、以下のコードを追加してください。

function decodeBWT(data) {
  var decode_data = new Array();
 
  var len = data.shift().charCodeAt(0);
  var block_num = data.shift().charCodeAt(0);
  var BWT_BLOCK_LEN = len;
 
  for (var i = 0; i < block_num; i++) {
    var ary = data.slice(i*(BWT_BLOCK_LEN+1), (i+1)*(BWT_BLOCK_LEN+1));
    var line_no = ary.pop().charCodeAt(0);
 
    var first_col = new Array(ary.length);
    for (var j = 0; j < ary.length; j++) {
      first_col[j] = { ch:ary[j], index:j };
    }
 
    first_col.sort(function(a,b) { 
      if (a.ch != b.ch) {
        return a.ch.charCodeAt(0) - b.ch.charCodeAt(0);
      } else {
        return a.index - b.index;
      }
    });
 
    line = new Array(ary.length);
    for (var j = 0; j < ary.length; j++) {
      var f = first_col[line_no];
      line[j] = f.ch;
      line_no = f.index;
    }
 
    decode_data = decode_data.concat(line);
  }
 
  return decode_data.slice(0,len);
}
// 末尾2

4〜5行目

文字列の長さとブロック数を取り出します。

8行目

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

9行目

1ブロック分の文字列を切り出します。

10行目

元の文字列があった行数を取り出します。

12行目

ブロックの一番左の列を表す変数を宣言します。

13〜15行目

first_colに、1文字（ary[j]）とその行数（index）を格納していきます。行数を入れているのは安定ソートにするためと、その後の復元処理で使用するためです。

17〜23行目

first_colをソートします。文字の順、同じ文字なら元の並びを保ったままソートします。

25〜30行目

先ほど説明したロジックのとおり元の文字列を復元していきます。

ブロックソーティングの実装（2）　実行部分

　残りは実行部分のコードです。先ほどのコード「// 末尾2」の次の行に追加してください。

function execBWT(input, output) {
  var data = getStringById(input);
  var element = document.getElementById(output);
  element.innerHTML = "元のデータ量: " + data.length + "<br>";
 
  var encode_data = encodeBWT(data);
  if (encode_data == null) { return; }
  element.innerHTML += "変換しました。<br>";
  element.innerHTML += "変換後のデータ量: " + encode_data.length + "<br>";
  element.innerHTML += "変換後のデータ:<br/> " + encode_data.join("") + "<br>";
  element.innerHTML += "データを復元します。<br>";
 
  var decode_data = decodeBWT(encode_data.clone());
  if (decode_data == null) { return; }
 
  element.innerHTML += decode_data.join("");
}
</script>
<br/>
<input type="button" onClick="execBWT('area1','area2');" value="BWT">
<!-- 末尾3 -->

　それでは実行してみましょう。Internet Explorerだと10秒以上かかるかもしれません。変換後のデータを見ると、元の文字列に比べて連続した文字が多くなっていることが分かると思います。