🐥
ランレングス圧縮とは？
ランレングス圧縮とは？
ABC380,381でランレングス圧縮(run length encoding、略してRLE)というアルゴリズムを用いた解き方が説明されていたので、理解する。
以下記事によるとランレングス圧縮とは、同じ文字が連続して何文字出現するを求めるアルゴリズム
ランレングス圧縮（ランレングス符号化）とは、データの圧縮方法の一つで、圧縮前に正確に復元することができる可逆圧縮の一種です。
同じ文字が連続して何文字出現するかに変換します。
例えば、01110001100という文字列の場合、ランレングス圧縮をvector<P<char,int>>で表すとこんな感じ
[('0',1),('1',3),('0',3),('1',2),('0',2)]
RLEのテンプレートコードは以下、そこまで複雑ではない。
string s;
cin >> s;
// run length encoding
vector<pair<char,int>> rle;
for(char c:s) {
// サイズチェックをしないとbackメソッドで配列外参照になるためサイズが0でないことを判定
if (rle.size() && rle.back().first == c) rle.back().second++;
else rle.emplace_back(c,1);
}
例題
Discussion