ランレングス圧縮と復元

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: ランレングス圧縮を行う
    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;
}

C++での実装例（pair型を用いる場合）

先程の実装例では数字が文字列中に出現する場合は正しく実行できません。encode する際に文字 c と出現回数を分けて、pair 型で vector などに保存すると正しく decode できます。

/* encode: ランレングス圧縮を行う
*/
vector<pair<char, int>> encode(const string& str) {
    int n = (int)str.size();
    vector<pair<char, int>> ret;
    for (int l = 0; l < n;) {
        int r = l + 1;
        for (; r < n && str[l] == str[r]; r++) {};
        ret.push_back({str[l], r - l});
        l = r;
    }
    return ret;
}

/* decode: ランレングス圧縮の復元を行う
*/
string decode(const vector<pair<char, int>>& code) {
    string ret = "";
    for (auto p : code) {
        for (int i = 0; i < p.second; i++) {
            ret.push_back(p.first);
        }
    }
    return ret;
}

練習問題

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