「圧縮と解凍」
～マンガでプログラミング用語解説

マンガで分かるプログラミング用語辞典（64）

解説

　圧縮と解凍は、コンピュータを利用していると必ずと言ってよいほど遭遇する言葉です。

　圧縮は、データをアルゴリズム（一定の手順）によってコンパクトにまとめることです。解凍はその逆で、圧縮されたファイルを元に戻すことです。

　圧縮アルゴリズムは、様々な方式が研究されており、多くのソフトウェアに組み込まれています。その方式の中から、いくつかを紹介します。

　まずは、単純に出現数を置き換えたものです。同じようなデータが連続する場合に高い圧縮率となります。しかし、現実のファイルでは、あまり使う機会がないでしょう。

ＡＡＡＢＢＢＢＢＡＡＡＡ
↓
Ａが３回、Ｂが５回、Ａが４回
↓
Ａ３Ｂ５Ａ４

　次は、辞書を作りながら圧縮していく方式です。単純な文字数よりも複雑です。「辞書にある文字＋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

フィードバックお待ちしております！

　ご感想、解説して欲しい用語、解説内容のアドバイスなどございましたら、FacebookやTwitterなどでお気軽に編集部までお寄せください。よろしくお願いいたします。