データ量を操る圧縮／展開を究めよう：コーディングに役立つ！ アルゴリズムの基本（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％くらいになったと思います。
今回のようなアスキーアートに対する圧縮率はいまひとつですが、ランレングス法は白黒の画像データを圧縮する場合などに効果を発揮します。
Copyright © ITmedia, Inc. All Rights Reserved.