Pythonで文字列圧縮（ランレングス圧縮）を実行するプログラムの書き方

はじめに

文字列圧縮のアルゴリズムとしてよく知られているのが「ランレングス圧縮（Run Length Encoding：RLE）」です。これは、同じ文字が連続して現れる回数を数えて、その情報をもとに文字列を短く変換する手法です。

例えば、'bbbb' のように文字 'b' が4回連続している場合、エンコード後は 'b4' となります。ただし、1回しか出現しない文字については、カウント数を付けずにそのまま出力します。

問題の例

入力として次の文字列が与えられたとします。

s = "abbbaaaaaaccdaaab"

この場合、期待される出力は以下の通りです。

ab3a6c2da3b

内訳を見てみると、a が1回 → a、b が3回 → b3、a が6回 → a6、c が2回 → c2、d が1回 → d、a が3回 → a3、最後に b が1回 → b となり、連結すると ab3a6c2da3b になります。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• 結果を格納するための空文字列 res を用意し、カウンタ cnt を 1 で初期化します。
• インデックス 1 から文字列の末尾までループ処理を行います。
• 現在の文字 s[i] と直前の文字 s[i-1] が同じ場合は、cnt を +1 します。
• 異なる場合は、直前の文字と（カウントが1より大きければ）そのカウント数を res に追加し、cnt を 1 にリセットします。
• ループ終了後、最後の文字と（必要であれば）カウント数を res に追加します。
• 最終的な res を返します。

実装例

それでは、実際のPythonコードを見てみましょう。

def solve(s):
    res = ""
    cnt = 1
    for i in range(1, len(s)):
        if s[i - 1] == s[i]:
            cnt += 1
        else:
            res = res + s[i - 1]
            if cnt > 1:
                res += str(cnt)
            cnt = 1
    res = res + s[-1]
    if cnt > 1:
        res += str(cnt)
    return res

s = "abbbaaaaaaccdaaab"
print(solve(s))

入力

"abbbaaaaaaccdaaab"

出力

ab3a6c2da3b

計算量について

このアルゴリズムの時間計算量は O(n) です。ここで n は入力文字列の長さを表します。文字列を一度だけ走査すればよいため、非常に効率的な処理が可能です。

ただし、上記のコードでは res = res + s[i - 1] のように文字列の連結を繰り返しています。Pythonでは文字列はイミュータブル（変更不可）であるため、連結のたびに新しい文字列オブジェクトが生成され、最悪の場合 O(n²) のオーバーヘッドが発生します。

より効率的にしたい場合は、リストに要素を追加していき、最後に join() で結合する方法が推奨されます。

def solve(s):
    if not s:
        return ""
    res = []
    cnt = 1
    for i in range(1, len(s)):
        if s[i - 1] == s[i]:
            cnt += 1
        else:
            res.append(s[i - 1])
            if cnt > 1:
                res.append(str(cnt))
            cnt = 1
    res.append(s[-1])
    if cnt > 1:
        res.append(str(cnt))
    return "".join(res)

まとめ

ランレングス圧縮は、同じ文字が長く連続するデータ（画像データなど）に対して特に効果を発揮するシンプルな圧縮手法です。一方で、文字の重複が少ないテキストでは逆に文字列が長くなる場合がある点には注意が必要です。本記事で紹介した実装を参考に、ぜひ自分でも試してみてください。