ランレングス圧縮と復元

その他圧縮, 復元, ランレングス圧縮

ランレングス圧縮(ランレングス符号化)とは、データの圧縮方法の一つで、圧縮前に正確に復元することができる可逆圧縮の一種です。

同じ文字が連続して何文字出現するかに変換します。

例:

In: aaallgoooooo
Out: a3l2g1o6

圧縮(encode)する際は Run Length Encoding, 復元(decode)する際は Run Length Decoding と言います。

アルゴリズム

ランレングス符号化: Encoding

  • 以下を符号化したい文字列 S が空になるまで繰り返す
    1. S の最初の文字 c について、c が連続で何回出現するかを数えて、違う文字が出現するまで取り出す
    2. 答えの文字列に、c と 出現回数を後ろから加える

※ 「abcdefghijk」 が符号化で「a1b1c1d1e1f1g1h1i1j1k1」になるように、符号化前よりも、符号化後の方が文字列が長くなる場合があるので注意が必要です。

ランレングス符号化の復元: Decodeing

  • 以下を復元したい文字列 S’ が空になるまで繰り返す
    1. S’ の最初の文字 c について、c とc が連続で何回出現するかを取り出す
    2. 答えの文字列に、c とを出現回数だけ加える

計算量

  • 符号化:\(O(N)\)
  • 復元:\(O(N)\)

もとの文字列のサイズをとすると、どちらも\(O(N)\) で計算できます。

C++での実装例

同じ文字列が連続で何回出現するのかなどを数える際は、しゃくとり法のように実装するとやりやすいでしょう。

※以下の実装例では、もとの文字列に数字が出現しないことを前提にしています。仮に出現する場合は、decode が正しくできません。

※数字が出現する場合は、encode する際に文字 c と出現回数を分けて、pair 型で vector などに保存すると正しく decode できます。

練習問題