ランレングス符号化をpythonで
タイトルに反して、実はやりたかったのは符号化ではなく、下の本の最初の「帽子の問題」。
問題は、前向き/後向きバラバラに帽子を被った人たちが一列に並んでいる状況で、整理員が指示を出して全員の帽子を同じ方向になる様にする、というもの。指示は「○番から×番の人」のように範囲で指定できます。なるべく少ない回数でそれを達成するにはどうしたらよいか、というわけです。
パッとみただけで「あ、これランレングスみたいなのして偶奇で判定だ」とは閃いたので、本は読まずに見切り発車始めてしまったのですが、ここで、はて、ランレングスってどう書くのがエレガントかなー、と脱線し始め、そちらの迷宮にハマってしまった、というパターンですかっこわるー(実際この本でも迂回しながらランレングス圧縮にランディングしてます。合わせてLZのような話も出ていました）。一般のランレングスの場合、処理対象はあらゆる記号、かつ、出るタイミングはランダムですが、この問題では前向き(F), 後向き(B)が必ず交互に出流ので、もっと簡単にできそうです。そこまでやらんけどなー。
まずはナイーブに…
ベースラインとして、まずは単純極まりない、Cで書いたらこうなる、みたいなのを書く、がセオリーだと思うのですが、そこは脊髄反射プログラマの私なので、最初に考えついた方法で猪突実装してしまいました。内容は 1 runを一気に消したい→lstripで最初の文字を剥がしちゃえ、でした。
def rle_strip(s): while s: c = s[0] striped = s.lstrip(c) yield((c, len(s) - len(striped))) s = striped
lstrip()で剥がして、元の長さから剥いだ後の長さを引いて差を出していく、という単純ながらも、あれ、もうこれで良くね？ なアルゴリズムに見えます。ジェネレータイテレータとして実装したので、一個剥がすたびにyieldで次を返しています。
ついでなので単純極まりないほうも作っておきましょう（これが後からｶﾞﾋﾞｰﾝを産むことになるのですが…）
def rle_naive(s): prev = s[0] cnt = 1 for c in s: if prev != c: yield((prev, cnt)) cnt = 1 else: cnt += 1 prev = c yield((prev,cnt))
同じようにジェネレータイテレータとして実装しておきます。
pythonicな、あるいは numpy的な解法
python的、というより関数言語的というかリスト処理的というか、並列にできるもんはリストで並べてしまう戦略*1。
numpy使うなら結構簡単でずらしたndarray同士で比較した ndarray作って、nonzero()またはwhere()で場所を拾う、というよくある戦略で良いです。
def rle_numpy(s): o = _succ(s[-1]) # sentinel s = np.array(list(s+o)) idxs = np.append(-1, np.nonzero(s[1:] != s[:-1])[0]) return zip(s[idxs+1], idxs[1:] - idxs[:-1])
pythonicな、あるいはリスト内包な解法
上記numpy方式をリスト内包でできないかなーとやってみたのが次。僕のリスト内包の作り方って基本的に後ろから、「まずこれ作ってー、作ったやつでこうしてー」と思考の順番に前につなげて作ってしまう、、、
>>> list((lambda t: zip(t[1:],t))("good speed")) [('o', 'g'), ('o', 'o'), ('d', 'o'), (' ', 'd'), ('s', ' '), ('p', 's'), ('e', 'p'), ('e', 'e'), ('d', 'e')] >>> list((lambda t: (a!=b for a,b in zip(t[1:],t)))("good speed")) [True, False, True, True, True, True, True, False, True] >>> list((lambda t: compress(range(len(t)), (a!=b for a,b in zip(t[1:],t))))("good speed")) [0, 2, 3, 4, 5, 6, 8]
という癖があるので、いつも最終的に凶悪なのが生まれてしまいます…
(lambda s:(lambda a:[(s[q],p-q) for p,q in zip(a,[0]+a)])(list((lambda t:compress(range(len(t)),(a!=b for a,b in zip(t[1:],t)))) (s[0]+s+chr(ord(s[-1])+1)))))("iiinnnputtt")
— 焼けてきたtkuro11 (@tkuro11) 2022年1月29日
[('i', 3), ('n', 3), ('p', 1), ('u', 1), ('t', 3)]
はい産まれましたーーーー(ムスカ大佐の目が見えなくなってしまうレベル)。
まあ清書して、
from itertools import compress def rle_wierd(s): o = _succ(s[-1]) # sentinel return [(s[q],p-q) for p,q in _pairwise(compress(range(len(s)+1), (a!=b for a,b in _pairwise(s+o,s[0]))) )]
とはしたものの、numpy使わない代わりにitertools.compressは使うは、pairwiseは実は無くなっていたことに気が付かず、自前で作ることになるはでもうダメダメwww
あ、この辺で使っていた_pairwise, とか_succは以下です。
## utility routine ## (A, B, C, ..., Y, Z) -> ((0, A), (A,B), (B,C), ..., (Y,Z)) def _pairwise(seq, last = 0): for c in seq: yield(c, last) last = c # Next character in ASCII def _succ(c): return chr((ord(c)+1) % 255)
いやー盛大に自爆！
しかもー
ベンチとってみて氏ぬ。M1 Macbook Airでやってみました。
tkuro@carnalite ~/00PlayGround/5265da25fd296305141db600c27095d4 % sysctl machdep.cpu.brand_string machdep.cpu.brand_string: Apple M1 tkuro@carnalite ~/00PlayGround/5265da25fd296305141db600c27095d4 % ./runlength_test.py ***** --- run-length 1 (totally random) --- ***** # rle_naive 0.724449584 # rle_strip 2.3304234999999998 # rle_numpy 2.630215708 # rle_wierd 1.5978349170000001 ----------- ***** --- run-length 10 aaaa bbbb --- ***** # rle_naive 0.33949912500000057 # rle_strip 0.2601713329999997 # rle_numpy 1.0721955419999993 # rle_wierd 0.8074890840000002 ----------- ***** --- run-length 100 aaaa bbbb --- ***** # rle_naive 0.2919787500000002 # rle_strip 0.05756099999999975 # rle_numpy 0.930163125 # rle_wierd 0.7280477919999999 ***** --- run-length natural language --- ***** # rle_naive 0.4841780419999999 # rle_strip 2.0906731670000003 # rle_numpy 1.9265417080000002 # rle_wierd 1.1903997910000008
なななななななななんと、numpyが一番遅い！！！！
しかもnaiveが一番まともじゃないですか。stripはrunが長くなってくるとゲキ強いですが、それにしても何の工夫もしてない奴が一番早くって、一番苦労したwierdがあんまり報われないとか、これはひどいなー。絶倫にアウトじゃないですか。
まあでもやっていることを考えるとそれはそうか、という気もしますね。２リストを全部見ていくよりも１リスト１イテレーションの方が軽いですね。
encoder & decoder
とりあえず目的はこれじゃないんだけど、一応遊んでみるために書いておきました。-nで最小ラン長を指定できる様にしておいた。
encoder
from runlength_test import rle_naive import argparse parser = argparse.ArgumentParser() parser.add_argument('-n', '--num', action="store", dest="num", default=1, type=int) parser.add_argument('filename', type=str, nargs="?") args = parser.parse_args() n = args.num if args.filename: f = open(args.filename) else: import sys f = sys.stdin code = rle_naive(f.read()) ret = "" for c, l in code: if l >= n: ret += str(c) * n ret += chr(l-n) else: ret += c * l print(ret)
decoder
from runlength_test import rle_naive import argparse parser = argparse.ArgumentParser() parser.add_argument('-n', '--num', action="store", dest="num", default=1, type=int) parser.add_argument('filename', type=str, nargs="?") args = parser.parse_args() if args.filename: f = open(args.filename) else: import sys f = sys.stdin text = f.read() cnt = 0 last = ret = "" for c in text: if cnt >= args.num: ret += last * ord(c) cnt = 0 else: ret += c if last != c: cnt = 0 cnt += 1 last = c print(ret)
Alice in worderlandのrabitholeのところを拾ってきて圧縮？してみた
tkuro@carnalite ~/00PlayGround/5265da25fd296305141db600c27095d4 % ./encoder.py alice_down_the_rabithole.txt > alice_n1.comp tkuro@carnalite ~/00PlayGround/5265da25fd296305141db600c27095d4 % ./encoder.py alice_down_the_rabithole.txt -n2 > alice_n2.comp tkuro@carnalite ~/00PlayGround/5265da25fd296305141db600c27095d4 % ./encoder.py alice_down_the_rabithole.txt -n3 > alice_n3.comp tkuro@carnalite ~/00PlayGround/5265da25fd296305141db600c27095d4 % ls -l alice_* -rw-r--r-- 1 tkuro staff 11725 2 3 00:12 alice_down_the_rabithole.txt -rw-r--r-- 1 tkuro staff 22383 2 3 01:00 alice_n1.comp -rw-r--r-- 1 tkuro staff 11867 2 3 01:00 alice_n2.comp -rw-r--r-- 1 tkuro staff 11658 2 3 01:01 alice_n3.comp
あーやっぱりランをある程度伸ばさないと普通のテキストは難しいですねー。3でやっと元ファイルより小さくなった。
SRLEとかLZとか、ちょっと面倒なので今回はパス。
教訓
- numpy的な書き方は楽しいけど、いらんことをいらんふうにやってしまうと、素朴なアルゴリズムの方が素朴なだけに速いことが多い
- リスト内包表現は楽しいけど、（ry
- 案外最初のひらめきが良かったりする
- ランレングスは普通の文章には難しいややっぱ
我ながらしょうもないことばかりやっているなあ、と思いました。
今回のはここに置いておきました。
runlength_test.py · GitHub
*1:こういうのなんていうんだろう
