pythonによるランレングス圧縮

概要

pythonでランレングス圧縮がしたくなった時に、パッと確認するための備忘録です。

ランレングス圧縮について

ランレングス圧縮とは、データを圧縮するためのアルゴリズムの一つで、連続して現れる文字を、繰り返した回数で置き換える方法です。
例えば、"AAAABBBBBCC"のような文字列があった際に、"A4B5C2"のように、Aが４回、Bが５回、Cが２回出現したといった形で置き換えを行います。

実装について

自分はこちらの問題で利用したため、端から文字列を順にたどっていき、配列に格納する流れで実装しました。
以下の実装では、文字列の長さ分の計算量となっています。

※もっと高速にできる、メモリの消費を抑えるために、こうした方が良いなどあれば、是非コメントお願いします。

def rle(s):
  bef = s[0]
  cnt = 1
  arr = []
  for i in range(1, len(s)):
    if s[i] == bef:
      cnt += 1
    else:
      arr.append([bef, cnt])
      bef = s[i]
      cnt = 1
  arr.append([bef, cnt])
  return arr