アルゴリズム初心者向けの基礎と入門(C#, Pythonとか)

ランレングス圧縮 (連長圧縮)

ランレングス圧縮 (RLE: Run Length Encoding) とは、データ圧縮アルゴリズムの一種で、可逆圧縮に分類されます。このアルゴリズムでは、ある連続したデータをデータ1つ分と連続した長さで表して圧縮します。例えば "AAAAA" を "A" が 5回続くデータなので、 "A5" という風に圧縮します。

FAXや単純な画像データについて利用されるアルゴリズムです。

特徴

「データ * 連続回数」の形に変換することになるので、1つのデータが長く続くデータや、そもそも出現するデータの種類が少ないデータなどは、圧縮効率が高くなる傾向にあります。

逆に、データがあまり連続しないデータについては、圧縮効率が悪いどころか圧縮前よりデータサイズが大きくなってしまうこともあります。例えば "ABCDE" という5文字を「データ * 連続回数」の形に変換すると "A1B1C1D1E1" となり2倍のサイズになってしまいます。

連続しないデータでも圧縮効率を下げないように改良したアルゴリズムとして、PickBits と呼ばれる方法もあります。

PickBits

上述の通り、ランレングス圧縮は連続しないデータ部分の圧縮効率が悪いどころか、逆にデータ量が増えてしまいます。その欠点を改良したものが、PickBits と呼ばれるアルゴリズムです。基本的な考え方は変わらないのですが、連続しないデータ部分が続く部分をフラグ管理することで圧縮率を高めます。

"AAABCDEE" という文字を通常のランレングス圧縮で圧縮すると、"A3B1C1D1E2" となり元のデータより大きなデータになってしまいます。これを PickBits では次のように圧縮します。

"A3-3BCDE2"

PickBits では連続しないデータが続く部分についてカウントし、「-(カウント) + 連続しないデータ」として表現します。上記の例では "-3BCD" の部分に該当します。これは 3つのデータ "B", "C", "D" について連続しない(つまり1文字のみ)という意味になります。

通常圧縮は上記のように文字列で見るのではなく、バイト単位で圧縮を行います。したがって、1ビット分をマイナスのフラグとして使うと、連続数として表せるのが最大128までとなります。これ以上の連続するデータ部分が通常のランレングス圧縮に比べ圧縮効率が低下してしまいます。

サンプルコード

圧縮対象のファイルを通常のランレングス圧縮を用いて圧縮したファイルを生成するサンプルコードです。バイト単位で読み込んだファイル内容から圧縮ファイルを生成します。また生成した圧縮ファイルを元に戻す(解凍する)ことで圧縮前のファイルと同等のファイルを生成します。

以下のようなモノクロビットマップ画像は非常に効率の良い圧縮が行われますが、日本語のテキストファイルなどはあまり効率よく圧縮されません。

C#

using System.Collections.Generic;
using System.IO;
using System.Linq;

public static class RLE
{
    public static void RLE__(string inputFile, string outputFile)
    {
        // ファイル内容読込
        var bytes = File.ReadAllBytes(inputFile);

        // ランレングス圧縮
        var enc = EncodingRunLength(bytes);

        // 圧縮内容書き込み
        File.WriteAllBytes(outputFile, enc);

        // 回答内容書き込み
        var dec = DecodingRunLength(enc);
        File.WriteAllBytes($"{inputFile}_dec.txt", dec);
    }

    // 圧縮
    public static void Encode(string inputFile, string outputFile)
    {
        // ファイル内容読込
        var bytes = File.ReadAllBytes(inputFile);
        // ランレングス圧縮
        var enc = EncodingRunLength(bytes);
        // 圧縮内容書き込み
        File.WriteAllBytes(outputFile, enc);
    }

    // 解凍
    public static void Decode(string inputFile, string outputFile)
    {
        // ファイル内容読込
        var bytes = File.ReadAllBytes(inputFile);
        // 解凍
        var dec = DecodingRunLength(bytes);
        // 解凍内容書き込み
        File.WriteAllBytes(outputFile, dec);
    }

    // ランレングス圧縮を行う
    private static byte[] EncodingRunLength(byte[] bytes)
    {
        var result = new List<byte>();

        int length = 0;
        byte b = 0;

        for (int i = 0; i < bytes.Length; i++)
        {
            if (i == 0)
            {
                // 1文字目の場合保持
                length = 1;
                b = bytes[0];
            }
            else if (bytes[i] == b)
            {
                // 直前の文字と一致していればカウントアップ
                length++;
            }

            // 不一致のタイミングで出力
            if (bytes[i] != b)
            {
                result.AddRange(GetRunLength(b, length));

                // 文字データ更新
                length = 1;
                b = bytes[i];
            }
        }

        // 最後の圧縮結果を出力
        result.AddRange(GetRunLength(b, length));

        return result.ToArray();
    }

    // 文字と連続数から圧縮結果文字列を生成
    private static byte[] GetRunLength(byte b, int length)
    {
        // A, 256 のデータから { A, 255, A, 1 } という配列を返す
        var result = new List<byte>();
        const int MaxLength = 255;  // 1バイトで表現できる最大値

        for (int i = 1; i <= length; i++)
        {
            if (i % MaxLength == 0)
            {
                result.Add(b);
                result.Add(MaxLength);
            }
            else if (i == length)
            {
                // 最終文字数時点で出力
                result.Add(b);
                result.Add((byte)(length % MaxLength));
            }
        }

        return result.ToArray();
    }

    // ランレングス圧縮されたデータを解凍
    private static byte[] DecodingRunLength(byte[] bytes)
    {
        var result = new List<byte>();
        byte b = 0;
        for (int i = 0; i < bytes.Length; i++)
        {
            // 偶数番目には文字, 奇数番目にはデータ長
            if (i % 2 == 0)
            {
                b = bytes[i];
            }
            else
            {
                // データの長さ分バイトデータを作成し末尾に追加
                result.AddRange(Enumerable.Repeat(b, bytes[i]));
            }
        }
        return result.ToArray();
    }
}