#Pythonで学ぶアルゴリズム< 圧縮アルゴリズム >
はじめに
基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第31弾として圧縮アルゴリズムを扱う．
圧縮アルゴリズム
同じ文字が連続する場合，その文字の出現回数を数えて圧縮するアルゴリズム．例えば，0と1の２つの文字だけで構成される文字を表現する．これは，FAXの圧縮などで使われている方法．
実装
上の説明に従って，Pythonでの実装を行う．ただし，ここでは0と1の２つの文字と限定するのではなく，任意に与えられ文字列を自動で圧縮してくれるプログラムを組むこととした．さらに，後で元のデータの復元ができるように，何を圧縮したのかの記録も出力できるものとしている．詳しくは，ソースコードの中で説明している．以下にソースコードとそのときの出力を示す．
ソースコード
"""
2021/02/05
@Yuya Shimizu
圧縮アルゴリズム
"""
def compress(data):
counter = {} #各要素の連続出現数を格納する辞書型配列
count_chr = data[0] #カウントすべき文字を格納する変数
factors =[count_chr] #カウントする文字を順に格納する配列
i = 0 #カウントする文字の変更回数を0から数える変数
counter[i] = 0 #i番目の文字の出現数を0で初期化
for factor in data:
if count_chr != factor:
"""文字の連続が途切れたら以下を実行"""
count_chr = factor #カウントすべき文字を更新
factors.append(count_chr) #カウントする文字を順に格納
i += 1 #カウントする文字の変更回数を1増加
counter[i] = 0 #i番目の文字の出現数を0で初期化
counter[i] += 1 #i番目の文字の出現数を1増加
new_data = []
[new_data.append(counter[j]) for j in range(len(factors))]
return [new_data, factors] #圧縮されたデータと，その各要素を返す
if __name__ == '__main__':
DATA = '000111000022455666aaauuああああ'
compressed_data, factors = compress(DATA)
print(f"{DATA} → {compressed_data} (factors: {factors})")
出力
000111000022455666aaauuああああ → [3, 3, 4, 2, 1, 2, 3, 3, 2, 4] (factors: ['0', '1', '0', '2', '4', '5', '6', 'a', 'u', 'あ'])
確かに，0と1以外であっても対応できており，さらに数字以外の文字であっても対応できていることも分かる．
感想
今回をもって，今まで使ってきていた参考書（参考文献）の学習が終了した．これでとりあえず基本的なアルゴリズムを少しは学べたこととする．ただし，アルゴリズムはまだまだ数多く存在し，まだ学ぶべきものは多くあるはずである．また，今後学習を進める中で，新たに学習すべきものも出てくるであろう．よって，「Pythonで学ぶアルゴリズム」のシリーズが終わるわけではない．これが終わる時は，Pythonで学ぶアルゴリズムがこの世からなくなるときである．しかし，それはないだろう．学びに終わりはないと思っている．
次回からは，「Javaによるはじめてのアルゴリズム入門 河西 朝雄 著 技術評論社」という参考書を使って学習を進めることとする．この教材はなかなか分厚いが，今回学んだものと一部重複するところもあるため，効率よく進めていきたい．
参考文献
Pythonで始めるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量
増井 敏克 著 翔泳社