ランレングス圧縮をpythonで実装する

アルゴリズムとデータ構造
記事内に広告が含まれています。
スポンサーリンク
スポンサーリンク

本記事の目標

  • 2通りの実装方法を知る
  • 具体的な応用例(AtCoder Beginner Contestの問題)

具体例

連続する要素を(値, 連続個数)の形式 で圧縮するアルゴリズムです。

例えば、

strings = "aabbbbbbbbbbbba" #圧縮前
↓
[('a', 2), ('b', 12), ('a', 1)] #圧縮後

実装コード

def rle(s):
    n = len(s) #文字列の長さ
    ans = [] #圧縮後のリスト
    l = 0 #始点
    while l<n:
        r = l+1
        while r<n and s[l]==s[r]: #異なる文字になるまで進む
            r += 1
        ans.append((s[l], r-l)) #文字,連続する個数
        l = r #連続しなかった文字から探索を開始
    return ans

使い方

strings = "aabbbbbbbbbbbba" #圧縮前
print(rle(strings))
#[('a', 2), ('b', 12), ('a', 1)]

itertools.groupby()の利用

自分で実装しなくても、pythonの標準ライブラリにランレングス圧縮を実行できる関数 itertools.groupby() が用意されています。

from itertools import groupby
strings = "aabbbbbbbbbbbba" #圧縮前

ans = [(k, len(list(g))) for k,g in groupby(strings)]
print(ans)
#[('a', 2), ('b', 12), ('a', 1)]

応用例: AtCoder Beginner Contest 283: C

応用例として、以下の問題をランレングス圧縮を使って解いてみます。

高橋君は、レジ打ちの仕事をしています。

レジの機械には 000123456789 の 11 個のボタンがあります。 レジの機械には、はじめ 00 が表示されています。 ボタン 00 を押すと、表示されている数が 100 倍されます。 それ以外のボタンを押すと、表示されている数が 10 倍されたあとに、押されたボタンに書かれている数が加算されます。

高橋君は、レジに整数 S を表示させたいです。 レジに S が表示されている状態にするためには、少なくとも何回ボタンを押す必要があるか求めてください。

AtCoder Beginner Contest 283 C: Cash Register

実装コード

def rle(s):
    n = len(s) #文字列の長さ
    ans = [] #圧縮後のリスト
    l = 0 #始点
    while l<n:
        r = l+1
        while r<n and s[l]==s[r]: #異なる文字になるまで進む
            r += 1
        ans.append((s[l], r-l)) #文字,連続する個数
        l = r #連続しなかった文字から探索を開始
    return ans

if __name__ == "__main__":
    S = input()
    Nums = rle(S) #ランレングス圧縮
    
    ans = 0
    for string, num in Nums:
        #数字が0で、かつ 個数が偶数個の場合
        if string == "0" and num%2==0:
            ans += num//2
        #数字が0で、かつ 個数が奇数個の場合
        elif string =="0" and num%2==1:
            ans += num//2 + 1
        #0以外の数字
        else:
            ans += num
    print(ans)

例として、 $S=40004$ を入力した場合を考えます。

この時、ランレングス圧縮すると [('4', 1), ('0', 3), ('4', 1)] となります。

重要なのは数字が0の場合です。0が奇数個であれば、’00’を偶数回 + ‘0’を1回押すことが最適です。また、偶数個であれば、’00’を偶数回押すことが最適となります。

上記のコードで AC になることを確認できています。

まとめ

ランレングス圧縮の実装・利用方法についてまとめました。

自分で実装したコードは AtCoder Beginner Contest 019-B で正答になることは確認しています。

参考になれば幸いです

参考リンク: https://note.nkmk.me/python-itertools-groupby/

C - Cash Register
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

コメント