解説
圧縮と解凍は、コンピュータを利用していると必ずと言ってよいほど遭遇する言葉です。
圧縮は、データをアルゴリズム（一定の手順）によってコンパクトにまとめることです。解凍はその逆で、圧縮されたファイルを元に戻すことです。
圧縮アルゴリズムは、様々な方式が研究されており、多くのソフトウェアに組み込まれています。その方式の中から、いくつかを紹介します。
まずは、単純に出現数を置き換えたものです。同じようなデータが連続する場合に高い圧縮率となります。しかし、現実のファイルでは、あまり使う機会がないでしょう。
ＡＡＡＢＢＢＢＢＡＡＡＡ ↓ Ａが３回、Ｂが５回、Ａが４回 ↓ Ａ３Ｂ５Ａ４
次は、辞書を作りながら圧縮していく方式です。単純な文字数よりも複雑です。「辞書にある文字＋1文字」を、辞書に追加しながら、データを「辞書の位置＋次の文字」に置き換えていきます。
ＡＢＡＢＡＢＡ…… ↓ ┏━━━━━━━━━━━━━┳━━━━━━━━━━┳━┳━━━━━┓ ┃圧縮したデータ ┃辞書に追加する文字 ┃ ┃辞書 ┃ ┣━━━━━━━━━━━━━╋━━━━━━━━━━╋━╋━━━━━┫ ┃ ┃0番目に空文字 ┃→┃０ ┃ ┃0番目の辞書の値＋A [0,A] ┃[Ａ]ＢＡＢＡＢＡ……┃→┃１ Ａ ┃ ┃0番目の辞書の値＋B [0,B] ┃Ａ[Ｂ]ＡＢＡＢＡ……┃→┃２ Ｂ ┃ ┃1番目の辞書の値＋B [1,B] ┃ＡＢ[ＡＢ]ＡＢＡ……┃→┃３ ＡＢ ┃ ┃3番目の辞書の値＋A [3,A] ┃ＡＢＡＢ[ＡＢＡ]……┃→┃４ ＡＢＡ┃ ┗━━━━━━━━━━━━━┻━━━━━━━━━━┻━┻━━━━━┛ ↓ [0,A][0,B][1,B][3,A]……
また、出現率で符号化する方法もあります。出現数でツリーを作っていき、出現数の多い文字ほど、短い符号で表すことで、圧縮を行います。
ＡＢＣＤＥＢＣＤＥＣＤＥ…… ↓ 出現率で木構造を作る ０／＼１ ／ ＼ Ｅ ０／＼１ Ｄ ＼ ０／＼１ Ｃ ＼ ０／＼１ Ｂ Ａ ↓ 一意の表を作れる ┏━┳━━━━┓ ┃Ｅ┃０ ┃ ┃Ｄ┃１０ ┃ ┃Ｃ┃１１０ ┃ ┃Ｂ┃１１１０┃ ┃Ａ┃１１１１┃ ┗━┻━━━━┛ ↓ bitの並び順で置き換える 1111 1110 110 10 0 1110 110 10 0 110 10 0……
他にも様々な圧縮アルゴリズムが存在します。興味のある人は、調べてみるとよいでしょう。
サンプル
簡単な「圧縮と解凍」のサンプルです。同じ文字が連続する場合は、数値に置き換えます。
<html>
<head>
<title>「圧縮と解凍」のサンプル</title>
</head>
<body>
<pre><script type="text/javascript">
// 元のデータと出力
var datSource = "AAAABBBBCCCCABCDEFDDDDDEEEEE";
document.writeln("元のデータ : " + datSource.length + "\n"
+ datSource + "\n");
// 圧縮
var datCmprss = datSource.replace(/(.)\1*/g,
function(s, s1, s2) {
if (s.length == 1) {return s;}
return s[0] + s.length;
}
);
// 圧縮後データと出力
document.writeln("圧縮後のデータ : " + datCmprss.length + "\n"
+ datCmprss + "\n");
// 解凍
var datDecmp = datCmprss.replace(/([A-Z])(\d*)/g,
function(s, s1, s2) {
if (s2 == "") {return s1;}
return new Array(s2 * 1 + 1).join(s1);
}
);
// 解凍後データと出力
document.writeln("解凍後のデータ : " + datDecmp.length + "\n"
+ datDecmp + "\n");
</script></pre>
</body>
</html>
出力結果
元のデータ : 28 AAAABBBBCCCCABCDEFDDDDDEEEEE 圧縮後のデータ : 16 A4B4C4ABCDEFD5E5 解凍後のデータ : 28 AAAABBBBCCCCABCDEFDDDDDEEEEE
