Pythonで文字列をランレングス符号化（RLE）するプログラムの書き方

文字列 s が与えられたとき、これをランレングス符号化（Run-Length Encoding）と呼ばれる手法でエンコードすることを考えます。

ランレングス符号化は、文字列を高速かつシンプルに圧縮できる手法の一つです。基本的なアイデアは、「連続して繰り返される同じ文字を、連続回数（カウント）＋その文字というペアに置き換える」というものです。

例えば、入力が s = "BBBBAAADDCBB" の場合、出力は "4B3A2D1C2B" となります。これは「Bが4個、Aが3個、Dが2個、Cが1個、Bが2個続いている」という意味を表しています。

アルゴリズムの手順

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

• 結果を格納する変数 res を空文字列で初期化します。
• 現在比較中の文字を保持する tmp に、文字列 s の最初の文字を代入します。
• カウンター count を 1 で初期化します。
• i を 1 から文字列の長さまでループさせます。
  • s[i] が tmp と異なる場合：res に count と tmp を連結した後、tmp を s[i] に更新し、count を 1 に戻します。
  • 同じ文字の場合：count を 1 増やします。
• ループ終了後、res に最後の count と tmp を連結して返します。

実装例

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

class Solution:
    def solve(self, s):
        res = ""
        tmp = s[0]
        count = 1
        for i in range(1, len(s)):
            if s[i] != tmp:
                res += str(count) + tmp
                tmp = s[i]
                count = 1
            else:
                count += 1
        return res + str(count) + tmp

ob = Solution()
print(ob.solve("BBBBAAADDCBB"))

入力

"BBBBAAADDCBB"

出力

4B3A2D1C2B

計算量と注意点

このアルゴリズムは文字列を先頭から一度だけ走査すればよいため、時間計算量は O(n)、必要なメモリも出力の長さに依存して O(n) となります。

なお、空文字列が入力された場合には s[0] の参照時に IndexError が発生するため、実運用では関数の冒頭に if not s: return "" のようなガード処理を追加しておくと安全です。