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

コーディングに役立つ! アルゴリズムの基本(8):データ量を操る圧縮/展開を究めよう (1/5)

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

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

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

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

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

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

ランレングス法

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

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

 例えば、

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行目

連続文字数lenが9未満で、前の文字cといまの文字が一致すればlenを1増やして次のループに移ります。

37〜40行目

前の文字といまの文字が違ったら文字と何文字連続したかを圧縮結果データに追加します。

42、43行目

現在の文字と長さをリセットして次のループに移ります。

54〜67行目

圧縮したデータを復元する関数です。

55行目

復元したデータも配列に格納します。

57行目

圧縮データに対してループします。

62〜64行目

文字数分ループして文字を追加していきます。

69〜88行目

ボタンを押したときに実行する関数です。圧縮を実行して画面に表示します。

90行目

ボタンです。

 さて、Webブラウザで実行してみましょう。Webブラウザの種類によってJavaScriptの内部実装が若干違うのでデータ量が少し変わってきますが、おおむね95%くらいになったと思います。

 今回のようなアスキーアートに対する圧縮率はいまひとつですが、ランレングス法は白黒の画像データを圧縮する場合などに効果を発揮します。

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

Copyright © ITmedia, Inc. All Rights Reserved.

RSSについて

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

メールマガジン登録

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