ランレングス圧縮と復元

2020年4月13日その他圧縮,復元,ランレングス圧縮

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

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

例:

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 できます。

/* encode: ランレングス圧縮を行う
    str内には数字が出現しないと仮定
*/
string encode(const string& str) {
    int n = (int)str.size();
    string ret = ""; // 答えを格納
    for (int l = 0; l < n;) {
        int r = l + 1;
        for (; r < n && str[l] == str[r]; r++) {};
        ret.push_back(str[l]);
        string num_str = to_string(r - l); // 出現回数
        ret += num_str;
        l = r;
    }
    return ret;
}

/* decode: ランレングス圧縮の復元を行う
    元の文字列には数字が出現しないと仮定
*/
string decode(const string& str) {
    int n = (int)str.size();
    string ret = ""; // 答えを格納
    for (int l = 0; l < n;) {
        int r = l + 1;
        for (; r < n && '0' <= str[r] && str[r] <= '9'; r++) {};
        int num = stoi(str.substr(l + 1, r - l)); // 出現回数
        for (int i = 0; i < num; i++) {
            ret.push_back(str[l]);
        }
        l = r;
    }
    return ret;
}

練習問題