[C#] ランレングス圧縮(連長圧縮)を実装する方法

C# でランレングス圧縮

• 連長圧縮 – Wikipedia

C# で ランレングス圧縮 を実装してみます。ランレングス圧縮についてはWkipediaを引用すると以下のようなものです。

連長圧縮は、データ圧縮アルゴリズムの一つで、可逆圧縮に分類される。ランレングス圧縮、RLE (Run Length Encoding) とも呼ばれる。

連長圧縮では、ある連続したデータを、そのデータ一つ分と連続した長さで表現することで圧縮している。
例えば、「A A A A A B B B B B B B B B A A A」は「A 5 B 9 A 3」と表せる。

同じデータが連続する場合はより圧縮後のデータサイズが小さくなりますが、データが連続していないと逆にデータサイズが大きくなる可能性もあります。例えば以下のようなデータです。

「A B C D」 -> 「A 1 B 1 C 1 D 1」

今回は文字列をランレングス圧縮するコードを実装してみます。

実装(タプルを使う)

static IEnumerable<(char, int)> RLE(string s)
{
    var count = 1;
    var prev = s[0];
    for (int i = 1; i < s.Length; i++)
    {
        if (prev == s[i])
        {
            count++;
        }
        else
        {
            yield return (prev, count);
            count = 1;
        }
        prev = s[i];
    }
    yield return (prev, count);
}

文字列を引数で受け取り、連続する文字列について (char, int) のタプルで文字と連続する文字数を返します。

ValueTuple<char, int> を使っています。たぶん .NET Framework 4.7 から実装されている新しい方のタプル型です。

Tupleを使うバージョン(古)

ValueTuple<char, int> を Tuple<char, int> にすれば .NET Framework 4.0 からでも使えます。

static IEnumerable<Tuple<char, int>> RLE(string s)
{
    var count = 1;
    var c = s[0];
    for (int i = 1; i < s.Length; i++)
    {
        if (c == s[i])
        {
            count++;
        }
        else
        {
            yield return Tuple.Create(c, count);
            count = 1;
        }
        c = s[i];
    }
    yield return Tuple.Create(c, count);
}

テスト

B – 高橋くんと文字列圧縮

AtCoder でランレングス圧縮の実装をそのまま問う問題があったのでこれで試して AC しました。ちなみに 2019年11月時点の AtCoder では C# のバージョンが古いので ValueTuple のほうは使えません。

以上。