YU2TA7KA's BLOG ~take one step at a time~

派生開発、組み込み開発周りのこと。

ランレングス圧縮の魅力 ~茶diff攻略への強い味方~

組み込みエンジニアをしているyu2ta7kaです。茶diff埋めをしているときに魅了されたランレングス圧縮について書きます。

0. はじめに

競技プログラミングサイトのAtCoderはすでに数百回のコンテストが開催され、その過去問は3,000を超えます。それらの問題は有志のAtCoder Problemsというツールによってdifficulty(色)が与えられており、これを参照することで自分の実力に合った問題に挑戦することができます。その中で入門(灰色)の次レベルにあたる茶色問題を解くにあたり、強い味方となる「ランレングス圧縮」について書きます。
ファクシミリ画像(余白の多い白黒2値画像)の圧縮などに用途例がありますが、本記事では競技プログラミングの問題を解く観点にフォーカスして書いていきます。

1. ランレングス圧縮(Run Length Encoding)とは

連続する文字列をその文字と連続する個数の2文字で表現することで、データを可逆圧縮するアルゴリズムです。
f:id:yuji-tanaak:20200813134536p:plain
数字も文字なので数字列に対してもランレングス圧縮は可能です。計算量はO(N)です。

2. ランレングス圧縮の効果

大きな入力データを圧縮できる

圧縮アルゴリズムの本義です。例えば、n = 10^{100}個という大きなデータ列であっても、それが全て同じaという文字であれば、a,1000とランレングス圧縮することで、扱うことが可能になります。

連続する同じ文字とその個数に着目するができる

文字列をランレングス圧縮することで、解答の実装がしやすくなります。
例えば、Kenken Raceという問題では、'.'で表現される何もないマスと'#'で岩があるマスが登場します。これらが、どれだけ続いているかを表現するためにランレングス圧縮をします。'...#...##...'は'.3#1.3#2.3'となります。pythonの二次元リストで表現したら、[[.,3],[#,1],[.,3],[#,2],[.,3]]となります*1。このリストデータを使って、制約を満たした状態で要求された操作が可能か判定するプログラムを実装することでAC*2できました*3

変化点のみに着目することができる

数字列をランレングス圧縮することで、変化点にフォーカスした実装がしやすくなります。
この効果をRoad to Millionaireという問題で知って、個人的には目からウロコで魅了されました。
Road to Millionaireは、予め株価の変動推移が与えられ、所持金を最大にするように株の売買をした結果を求める問題です*4。2日間で株価が変動しないところはその間で売買を行っても、変化がないため考慮が不要です。そこで、変動推移の数字列をランレングス圧縮してしまいます。そうすると圧縮後の数字列は変化点のみになり、この数値を使うことで株価変動無し時の考慮を省いて単純化して、売買アルゴリズムを実装するができるようになります!凄くないですか!?

3. ランレングス圧縮の魅力

ランレングス圧縮の効果を3つ挙げました。大きなデータを圧縮し、データサイズを小さくできる効果に加えて、抽象化してデータを考察、操作できるようになることが魅力と思います。また、簡単なアルゴリズムの割に応用範囲が広いところも良いなと思います。
問題を解いている中で、ランレングス圧縮することで視野が開ける感じを感じた瞬間が気持ち良いです。ランレングス圧縮に限らないのですが、データをうまく構造化することで見通しがよくなる快感は競技プログラミングをする中でACする次に気持ち良い瞬間ではないでしょうか?*5

4. ランレングス圧縮関連の問題例

問題名 ランレングス圧縮の用途
B - 高橋くんと文字列圧縮 まさにランレングス圧縮をやってみよう
D - Integer Cards 大きなデータを圧縮して扱う
A - Connection and Disconnection 連続する同じ文字と個数に着目するために抽象化
A - >< 連続する同じ文字と個数に着目するために抽象化
A - Kenken Race 連続する同じ文字と個数に着目するために抽象化
D - Gathering Children 連続する同じ文字と個数に着目するために抽象化
D - Road to Millionaire 変化点のみに着目するために抽象化、数字列に対する適用
C - Big Array 入力データがランレングス圧縮されたデータ。圧縮データを展開したときのことを考える問題とも捉えられる。

5. 実装例

 fn rle(s: Vec<char>) -> Vec<(char, u64)> {
     let mut res: Vec<(char, u64)> = Vec::new();
     let mut pre = ' ';
     let mut chain = 1;
 
     for c in s.into_iter() {
         if c == pre {
             chain += 1;
         } else {
             if pre != ' ' {
                 res.push((pre, chain));
             }
             pre = c;
             chain = 1;
         }
     }
     res.push((pre, chain));
     res
 }

6. おわりに

ランレングス圧縮が好きになってきたので、効果や魅力について書きました。この想いが少しでも伝われば幸いです。また、今後さらにいろいろなアルゴリズムを学び使えるようになっていき、他のアルゴリズムの魅力をお伝えできるようになれればと思います。

8. 競技プログラミング関連書籍

2020/10/2発売予定です。競プロ界隈でめちゃくちゃ丁寧な解説をQiitaやブログに書いてくれているけんちょんさんの書籍です。きっと素晴らしい本だと思います。

通称螺旋本と呼ばれる競プロ入門書の一つです。豊富なイメージ図や段落構成が工夫されており、非常に読みやすいです。基礎的な部分を固めてくれます。

*1:リスト[(タプル),(タプル),...]の表現もありです。

*2:ソースコードをジャッジサーバに送信し、Acceptされること

*3:このKenken Raceはランレングス圧縮をしなくても解くことは可能

*4:公式解説pdfでは、ランレングス圧縮はせずに解いています。

*5:ソートしたらO(N)で解けるようになる!がポピュラー。その次がランレングス圧縮な気がする。