データ圧縮の仕組みどうなっている？ランレングス圧縮を実装してみよう

• 

  ランレングス圧縮のプログラムを作って圧縮の仕組みを学ぼう

「圧縮」と「解凍」とは？

データの「圧縮」とは、データを何かしらの仕掛けを利用してサイズを小さくすることです。データサイズを小さくすることができれば、インターネットを通じてファイルを速く送信できますし、保存スペースも節約できます。そして「解凍」は圧縮したデータを元の状態のデータに戻すことです。

圧縮の仕組みは？

次に、どうすればデータを圧縮することができるのかを考えてみましょう。データを圧縮するためには、いくつかのアプローチがありますが、最も簡単なのは、「同じものや繰り返しをまとめて表現する」という方法です。

例えば、「リンゴリンゴリンゴリンゴ」というテキストデータがある場合には、「リンゴ×4」と表現するように工夫できます。元のテキストは12文字ですが、同じフレーズをまとめることで、5文字に圧縮することができます。なんと、半分以下にできました。

最も単純なランレングス圧縮を実現してみよう

なんとなく、圧縮の仕組みが分かったことでしょう。そこで、実際にプログラムを作って、圧縮に対する理解を深めてみましょう。ここで作るのは、「ランレングス圧縮(英語: Run-Length Encoding)」です。

ランレングス圧は、最も単純な圧縮アルゴリズムで、連続する文字をその個数で表現するという方法です。例えば、次の図にあるように「AAAABBBCCCCC」というデータであれば、その連続する個数を数えて「4A3B5C」と表現します。「AAABBBCCC」ならば「3A3B3C」になります。

• 

  ランレングス圧縮について

これを、なでしこで実装してみましょう。なでしこの貯蔵庫エディタに次のプログラムを入力してみましょう。

●(入力データを)ランレングス圧縮とは：
　　結果は空
　　個数＝0
　　前回C=入力データの1文字左部分
　　# --- 入力データを先頭から順に調べる --- (*1)
　　Cで入力データを反復：
　　　　もし、Cが前回Cならば：
　　　　　　個数を1増やす # --- (*2)
　　　　　　もし、個数＝9ならば：
　　　　　　　　結果＝結果＆「{個数}{C}」# --- (*3)
　　　　　　　　個数＝0
　　　　　　続ける。
　　　　結果＝結果＆「{個数}{前回C}」# --- (*4)
　　　　前回C=C
　　　　個数＝1
　　結果＝結果＆「{個数}{前回C}」
　　それは結果。

●(圧縮データを）ランレングス解凍とは：
　　結果＝「」
　　個数＝0
　　# 圧縮データを先頭から順に調べる ---- (*5)
　　Cで圧縮データを反復：
　　　　# 偶数なら繰り返し回数、奇数なら実際のデータ --- (*6)
　　　　もし、（対象キー％2）が0ならば：
　　　　　　個数＝INT(C)
　　　　違えば：
　　　　　　Cを個数でリフレインしてCCに代入。# --- (*7)
　　　　　　結果＝結果＆CC
　　それは結果。

# 実行テスト --- (*8)
元データ＝「AAABBBCCC」
圧縮データ＝元データをランレングス圧縮
解凍データ＝「3A3B3C」をランレングス解凍
「{元データ}→圧縮→{圧縮データ}」を表示。
「{圧縮データ}→解凍→{解凍データ}」を表示。

プログラムを実行してみましょう。エディタの下部にある「実行」ボタンを押します。すると、(＊8)で指定したテスト用のデータ「AAABBBCCC」を圧縮した結果「3A3B3C」と、圧縮したデータを解凍した結果である「AAABBBCCC」が表示されます。

• 

  プログラムを実行したところ

プログラムを確認してみましょう。まず、圧縮を行う関数「ランレングス圧縮」を見ていきましょう。(＊1)では入力されたデータを1文字ずつ先頭から確認します。それで、(＊2)では、前回と同じ文字があった時に個数を1増やすようにしています。(＊4)では前回と違った場合、変数「結果」に前回までの個数と文字を追記します。

なお、(＊3)では文字が10回以上繰り返される場合の対処を記述しています。今回のランレングス圧縮の実装では、必ず1文字ずつ「回数|文字|回数|文字|回数|文字…」と交互に繰り返すという仕様にしています。そこで、文字の繰り返し9回を超える場合には、結果にその文字を出力し、個数を0に戻すという処理を入れています。

次に解凍を行う関数「ランレングス解凍」を見てみましょう。(＊5)では圧縮データを1文字ずつ先頭から確認していきます。文字列を指定した「反復」で「対象キー」というのは繰り返し回数を0から順にカウントしている変数です。そこで、(＊6)で繰り返しの回数が偶数なら個数を記憶し、奇数であれば、その個数のデータを結果に追加する処理を行います。(＊7)では関数「リフレイン」を利用して指定個数の文字列を生成して結果に追加します。

(＊8)では実行テストとして、変数「元データ」を圧縮し、その結果を解凍して、どのようなデータができたのかを表示します。

画像を圧縮してみよう

画像データなどは、同じ色のデータが連続することが多いので、このような簡単なランレングス圧縮でもそれなりにデータを小さくできます。実際にどれくらい圧縮できるのか、簡単な画像エディタを作って試してみましょう。

プログラムは少し長くなるので、こちらにアップしました。プログラムを実行すると次の画面のように、8×8のドットエディタが表示されます。ドットをクリックすると、白黒が反転します。そして、ドットを変更する度に、元データの文字数、圧縮したデータの文字数と、実際の圧縮したデータを表示します。

次の画面のような、単純な画像であれば、だいたい元データの半分くらいになることが分かります。

• 

  数字の5を描いてみたところ - ランレングス圧縮で画像データはだいたい半分になった

他にもある圧縮のアルゴリズムの概要

なお、上記のように繰り返しをまとめるだけでは、それほど効率的な圧縮はできませんので、他の方法も紹介します。

有名な方法に「辞書を使って置き換える」という方法があります。これは、長い言葉やフレーズを短い記号に置き換えるというものです。例えば、「リンゴバナナミカンイチゴ」というテキストがあったとして、リンゴを「R」、バナナを「B」、ミカンを「M」、イチゴを「I」で置き換えるという規則を作ると「RBMI」というデータに置き換えることができます。元のデータは12文字ですが、4文字に圧縮できました。（もちろん、どのフレーズをどの記号に割り振るかという辞書や規則を最初に用意しておく必要があります。）

さらに「データの重要な部分だけを残す」という方法もあります。これは、画像や音声などで使われる手法ですが、画像であれば重要でない色を削ったり、音楽であれば人間の耳で聞き取れない部分を削ったりします。この方法を「非可逆圧縮」と呼びますが、圧縮したデータを解凍しても全く同じデータに戻すことができないという欠点があります。それでもデータを大幅に小さくできるので重宝されており、写真を圧縮したJPEG形式や音声を圧縮したMP3形式はこの方法で圧縮されています。

まとめ

以上、今回は実際にランレングス圧縮を実装して、圧縮の仕組みがどうなっているのかを確かめてみました。ランレングス圧縮の仕組みはとても簡単ですが、値の連続が多い画像データなどでは有効であることも確認できました。圧縮の仕組みを知るなら、普段から私たちが利用ししている圧縮という技術の利便性もいっそう感じることができるでしょう。

自由型プログラマー。くじらはんどにて、プログラミングの楽しさを伝える活動をしている。代表作に、日本語プログラミング言語「なでしこ」 、テキスト音楽「サクラ」など。2001年オンラインソフト大賞入賞、2004年度未踏ユース スーパークリエータ認定、2010年 OSS貢献者章受賞。技術書も多く執筆している。直近では、「シゴトがはかどる Python自動処理の教科書(マイナビ出版)」「すぐに使える!業務で実践できる! PythonによるAI・機械学習・深層学習アプリのつくり方 TensorFlow2対応(ソシム)」「マンガでざっくり学ぶPython(マイナビ出版)」など。