データ量を操る圧縮／展開を究めよう：コーディングに役立つ！アルゴリズムの基本（8）（1/5 ページ）

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

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

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

そういえば圧縮／展開って何をやっているの？

　読者の皆さまの中には、普段何げなくファイルを圧縮したり、圧縮されたファイルを展開したりしている方が多いと思います。

　ところで、これはどういう仕組みになっているかご存じでしょうか。

　今回はデータの圧縮の基本的な考え方を学び、実装を通してプログラミングのスキルを付けていきましょう。

ランレングス法

　まずは最も簡単な手法であるランレングス法について解説します。

　文字列のデータを圧縮することを考えます。同じ文字が多数連続している場合は、「文字」と「連続している文字数」のデータに変換することで圧縮できます。

　例えば、

aaaaabbbbbbccc

というデータの場合は、

a5b6c3

というふうに変換します。

　文字数で比較してみると、圧縮前は14文字でしたが圧縮後は6文字と半分以下になっています。圧縮後のデータから元のデータに戻すことも容易にできます。

ランレングス法の実装

　それでは早速、ランレングス法を実装してみましょう。サンプルデータは某巨大掲示板から引用しました。

<html>
<head>
<script type="text/javascript">
function getStringById(id) {
  var element = document.getElementById(id);
  return element.innerHTML;
}
</script>
</head>
<body>
<div id="area1">
<pre>
　　 ＿＿＿＿＿＿＿＿　　　　　　　　　　　　　＿＿＿＿＿＿＿＿
　 （＿＿＿＿＿　　　 ＼　　　　 ⊂⊃　　　　／　　　　＿＿＿＿）
　　　　（＿＿＿＿＿　　＼　　　∧＿∧　　 ／　　　＿＿＿＿）
　　　　　　　（＿＿＿＿　＼ （　´∀｀）／　＿＿＿＿）
　　　　　　　　　　（＿＿＿__⊂　　　 ⊃＿＿＿＿）
　　　　　　　　　　　　　　　 ｜ ｜ ｜
　　　　　　　　　　　　　　　（＿_）＿）
</pre>
</div>
<br>
 
<div id="area2"></div>
<script type="text/javascript">
function encodeRunLength(data) {
  var encode_data = new Array();
  var c;
  var len = 0;
 
for (var i = 0; i < data.length; i++) {
  if ((0 < len) && (len<9) && (c == data.charAt(i))) {
    len++;
    continue;
  }
 
  if(len != 0) {
    encode_data.push(c);
    encode_data.push(len);
  }
 
  c = data.charAt(i);
  len = 1;
  }
 
  if(len != 0) {
    encode_data.push(c);
    encode_data.push(len);
  }
 
  return encode_data;
}
 
function decodeRunLength(data) {
  var decode_data = new Array();
 
  for (var i = 0; i<data.length; i++) {
    if ((i%2) != 0) { continue; }
    var c = data[i];
    var num = parseInt(data[i+1]);
    if (isNaN(num)) { return null; }
    for (var j = 0; j < num; j++) {
    decode_data.push(c);
    }
  }
  return decode_data;
}
 
function execRunLength(input,output) {
  var data = getStringById(input);
  var element = document.getElementById(output);
  element.innerHTML = "元のデータ量: " + data.length + "<br>";
 
  var encode_data = encodeRunLength(data);
  if (encode_data == null) { return; }
 
  element.innerHTML += "圧縮しました。<br/>";
  element.innerHTML += "圧縮後のデータ量: " + encode_data.length + "<br/>";
  element.innerHTML += "データを復元します。<br/>";
 
  var decode_data = decodeRunLength(encode_data);
  if (decode_data == null) { return; }
 
  element.innerHTML += decode_data.join("");
  element.innerHTML += "<br/>圧縮率: ";
  element.innerHTML += parseInt(encode_data.length / data.length * 100);
  element.innerHTML += "%<br/>";
}
</script>
<input type="button" onClick="execRunLength('area1','area2');" value="RunLength">
<br><!-- 末尾1 -->
</body>
</html>

　プログラムを解説します。

11～21行目

圧縮する対象となるデータです。

24行目

結果表示用のdivタグです。

26～52行目

圧縮する関数です。

27行目

圧縮結果は配列に格納します。

31行目

元のデータを1文字ずつループします。

32～35行目