ゼロからはじめてみる日本語プログラミング「なでしこ」 第84回 データ圧縮の仕組みどうなっている？ランレングス圧縮を実装してみよう
2024年5月13日（月）9時39分 マイナビニュース
何かしらのファイルの受け渡しをする場合、ファイルを圧縮してから送信することでしょう。ファイルを圧縮するとファイルサイズが小さくなります。これは一体どういう仕組みなのでしょうか。今回は、最も簡単な圧縮アルゴリズム「ランレングス圧縮」を作って、その仕組みを確かめてみましょう。
○「圧縮」と「解凍」とは？
データの「圧縮」とは、データを何かしらの仕掛けを利用してサイズを小さくすることです。データサイズを小さくすることができれば、インターネットを通じてファイルを速く送信できますし、保存スペースも節約できます。そして「解凍」は圧縮したデータを元の状態のデータに戻すことです。
○圧縮の仕組みは？
次に、どうすればデータを圧縮することができるのかを考えてみましょう。データを圧縮するためには、いくつかのアプローチがありますが、最も簡単なのは、「同じものや繰り返しをまとめて表現する」という方法です。
例えば、「リンゴリンゴリンゴリンゴ」というテキストデータがある場合には、「リンゴ×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のドットエディタが表示されます。ドットをクリックすると、白黒が反転します。そして、ドットを変更する度に、元データの文字数、圧縮したデータの文字数と、実際の圧縮したデータを表示します。
次の画面のような、単純な画像であれば、だいたい元データの半分くらいになることが分かります。
.
○「圧縮」と「解凍」とは？
データの「圧縮」とは、データを何かしらの仕掛けを利用してサイズを小さくすることです。データサイズを小さくすることができれば、インターネットを通じてファイルを速く送信できますし、保存スペースも節約できます。そして「解凍」は圧縮したデータを元の状態のデータに戻すことです。
○圧縮の仕組みは？
次に、どうすればデータを圧縮することができるのかを考えてみましょう。データを圧縮するためには、いくつかのアプローチがありますが、最も簡単なのは、「同じものや繰り返しをまとめて表現する」という方法です。
例えば、「リンゴリンゴリンゴリンゴ」というテキストデータがある場合には、「リンゴ×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のドットエディタが表示されます。ドットをクリックすると、白黒が反転します。そして、ドットを変更する度に、元データの文字数、圧縮したデータの文字数と、実際の圧縮したデータを表示します。
次の画面のような、単純な画像であれば、だいたい元データの半分くらいになることが分かります。
.
関連記事（外部サイト）
