『問題解決のPythonプログラミング』という本を読んでいたら出てきたエクササイズです．おもしろそうだったのでやってみました．もともとその章のお題だった配列をぶん回すという方針に従って，それを応用して今回はやってみました．各文字に対してカウンタをもつ HashMap なり Dictionary をもたせるとよりシンプルになりそうな気がします（Python での Dictionary の書き方がまだ習得できておらず面倒でやってない）．
Disclaimer
Python 素人なのでもしかすると罠を踏んでいるかもしれません．
Run Length Encoding とは
たとえば次のような文字列があったとします．
BWWWWWBWWWW
この文字列を Run Length Encoding をもちいて圧縮すると次の文字列に圧縮されます．
1B5W1B4W
文字を1つ1つ分解して，重複して出てきた回数を文字の左に表示することで表現しています．当初は 11 byte (使用する言語により異なりそうですが，今回は便宜上1文字=1 byteと計算します) だった文字列の確保領域が 8 byte に減少しています．
実装してみる
さて，これを 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 ならわかる．
