Pythonでランレングス符号化された文字列をデコードするプログラム

ランレングス符号化とは

ランレングス符号化（Run-Length Encoding、RLE）は、文字列を高速かつシンプルに圧縮できる手法として広く知られています。その基本的な考え方は、「連続して繰り返される文字を、繰り返し回数と文字のペアとして表現する」というものです。

例えば、文字列 "BBBBAAADDCBB" の場合、Bが4回、Aが3回、Dが2回、Cが1回、Bが2回続いているため、"4B3A2D1C2B" とエンコードされます。

本記事では、この逆の処理、すなわちエンコードされた文字列を受け取り、元の文字列へと復元（デコード）するPythonプログラムを解説します。

問題の定義

ランレングス符号化された文字列 s が与えられたとき、そのデコード結果を求めます。

• 入力：s = "4B3A2D1C2B"
• 出力："BBBBAAADDCBB"

解法のアプローチ

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

1. デコード結果を格納するための空文字列 output を用意します。
2. 連続する数字を一時的に保持するための空文字列 num を用意します。
3. 文字列 s の各文字 i について次の処理を行います。
   • i がアルファベットの場合：これまでに読み取った数字（num）を整数に変換し、その回数だけ文字 i を output に追加します。その後、num を空にリセットします。
   • i が数字の場合：桁が複数ある場合にも対応できるよう、num に文字を連結して保持します。
4. すべての文字を処理し終えたら、output を返します。

数字を1桁ずつ文字列として蓄積してから変換している点がポイントです。これにより、「12A」のような2桁以上の繰り返し回数も正しく処理できます。

実装例

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

class Solution:
    def solve(self, s):
        output = ""
        num = ""
        for i in s:
            if i.isalpha():
                output += i * int(num)
                num = ""
            else:
                num += i
        return output

ob = Solution()
print(ob.solve("4B3A2D1C2B"))

入力

"4B3A2D1C2B"

出力

BBBBAAADDCBB

処理の流れを追ってみる

入力 "4B3A2D1C2B" の場合、プログラムは次のように動作します。

1. 「4」を読み込み、num = "4" となります。
2. 「B」を読み込むと、output に B×4 = "BBBB" が追加され、num はリセットされます。
3. 同様に「3A」→ "AAA"、「2D」→ "DD"、「1C」→ "C"、「2B」→ "BB" が順に追加されます。
4. 最終的に "BBBBAAADDCBB" が出力されます。

計算量について

このアルゴリズムは、入力文字列を一度だけ走査すればよいため、時間計算量は O(n)（n は入力文字列の長さ）です。ただし、Pythonの文字列連結は都度新しい文字列を生成するため、出力が非常に長くなる場合は list に追加して最後に join() で結合すると、より効率的になります。

まとめ

ランレングス符号化された文字列のデコードは、「数字部分を蓄積し、英字が出現した時点で繰り返し展開する」というシンプルなルールで実装できます。圧縮・伸長の基本概念を理解するのに最適な題材なので、ぜひ自分でもコードを書いて動作を確認してみてください。