競プロノート

Appearance

ランレングス圧縮（Run-Length Encoding） ​

同じ文字が連続する区間を、文字と連続回数の組にまとめるテクニック。

特徴 ​

項目内容
用途連続する同じ文字の集約
圧縮O(N)
復元O(N)（復元後の長さをNとする）
空間計算量O(K)（ラン数をKとする）

考え方 ​

連続する同じ文字を {文字, 個数} に変換する。

例えば、

text
AAABBCCCCA

を圧縮すると、

text
(A, 3), (B, 2), (C, 4), (A, 1)

となる。

同じ文字であっても、離れた位置にあれば別のランとして扱う。

実装 ​

cpp

#pragma once
#include <bits/stdc++.h>
using namespace std;

// ランレングス圧縮
vector<pair<char, int>> encode(const string& s) {
    vector<pair<char, int>> res;
    int n = (int)s.size();
    for (int l = 0; l < n;) {
        int r = l + 1;
        while (r < n && s[r] == s[l]) r++;
        res.emplace_back(s[l], r - l);
        l = r;
    }
    return res;
}

// ランレングス圧縮の復元
string decode(const vector<pair<char, int>>& code) {
    string res;
    for (auto [c, cnt] : code) {
        assert(cnt >= 0);
        res.append(cnt, c);
    }
    return res;
}

使用例 ​

圧縮 ​

cpp
string s = "AAABBCCCCA";
auto code = encode(s);

for (auto [c, cnt] : code) {
    cout << c << " " << cnt << '\n';
}

出力：

text
A 3
B 2
C 4
A 1

復元 ​

cpp
auto code = encode("AAABBCCCCA");
string s = decode(code);
// "AAABBCCCCA"

decode(encode(s)) == s が成立する。

典型的な応用 ​

連続区間の個数 ​

cpp
int cnt = encode(s).size();

最も長い連続区間 ​

cpp
int ans = 0;
for (auto [c, cnt] : encode(s)) ans = max(ans, cnt);

連続区間単位で処理 ​

cpp
auto code = encode(s);
for (int i = 0; i < (int)code.size(); i++) {
    auto [c, cnt] = code[i];
    // i番目のランを処理
}

元の文字列を1文字ずつ扱う代わりに、同じ文字が連続する区間を1つの要素として扱える。

注意点 ​

  • 圧縮後の各要素は {文字, 連続回数}。
  • 同じ文字でも連続していなければ別のランになる。
  • 空文字列を圧縮すると空配列になる。
  • ランレングス圧縮によって、必ずデータ量が小さくなるわけではない。
  • 今回の実装は char 単位なので、UTF-8の日本語などは文字単位ではなくバイト単位で扱われる。
  • 数値配列にも同じ考え方を適用できる。

関連 ​