Don't Repeat Yourself

Don't Repeat Yourself (DRY) is a principle of software development aimed at reducing repetition of all kinds. -- wikipedia

Run Length Encoding

『問題解決のPythonプログラミング』という本を読んでいたら出てきたエクササイズです.おもしろそうだったのでやってみました.もともとその章のお題だった配列をぶん回すという方針に従って,それを応用して今回はやってみました.各文字に対してカウンタをもつ HashMap なり Dictionary をもたせるとよりシンプルになりそうな気がします(Python での Dictionary の書き方がまだ習得できておらず面倒でやってない).

Disclaimer

Python 素人なのでもしかすると罠を踏んでいるかもしれません.

Run Length Encoding とは

たとえば次のような文字列があったとします.

BWWWWWBWWWW

この文字列を Run Length Encoding をもちいて圧縮すると次の文字列に圧縮されます.

1B5W1B4W

文字を1つ1つ分解して,重複して出てきた回数を文字の左に表示することで表現しています.当初は 11 byte (使用する言語により異なりそうですが,今回は便宜上1文字=1byteと計算します) だった文字列の確保領域が 8byte に減少しています.

実装してみる

さて,これを Python で実装してみました.

def run_length_encoding(strings) -> str:
    caps = list(strings)

    if len(caps) == 0:
        print('empty list')
        return ''

    caps = caps + ['#EOF']
    counter = 1
    encoded = ''

    for i in range(1, len(caps)):
        if caps[i] == caps[i-1]:
            counter += 1
        else:
            print(counter, caps[i-1], sep='', end='')
            encoded = encoded + str(counter) + caps[i-1]
            counter = 1  # counter reset

    return encoded

ポイントは #EOF という文字列を最後に追加しているところですね .caps という配列をインデックスで回して,前後の文字列が一致している限りはカウンターを動かすということをしています.異なった瞬間にプリントアウトしつつカウンターを初期値に戻しています.文字列が異なることを reduce のトリガーとするため,最後の #EOF を入れないと,最後の方の文字列のカウントがうまいこといきません.[*1]

さて,問題には decode もしろと書いてあったので decode もしましょう.1B5W1B4W という文字列を元に戻していきます.

def run_length_decoding(strings) -> str:
    caps = list(strings)

    if len(caps) == 0:
        print('empty list')
        return ''

    decoded = ''

    for i in range(1, len(caps)):
        if caps[i].isalpha():
            char = caps[i]
            count = caps[i-1]
            decoded = decoded + char * int(count)

    return decoded

また同様に,まずは文字列を分解して配列に直します.配列をインデックスで回します.アルファベットの箇所に到達したら,今回のエンコード方式ならばすぐ左に数字があるはずなので,その数字を取り出して回数分文字列を生成します.Python だと,文字列 * int で int の数値分文字列を生成できます.これを活用していきましょう.

アルゴリズムのカタログというよりは,目の前の問題をプロはどのように解いていくのか?という部分の解説に主眼を置いたいい本だなと思います.MIT の授業かなにかが書籍化したっぽいですね.私は CS の教育は受けていないので,こういう本が非常に助かります.Python なのも嬉しい.Python ならわかる.

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考

*1:この文字列,非常に危なっかしいですね.別のトークンを用意してあげる必要はありそうですが,まあ今回は本書の手法に従いたいのでそうしました.Map を使用すればこのようなことは必要ありません.