PythonワンライナーでBrainf*ckインタプリタ(第二部)
以前のストーリーはこちら： 西尾泰和のブログ: PythonワンライナーでBrainf*ckインタプリタ(第零部) 西尾泰和のブログ: PythonワンライナーでBrainf*ckインタプリタ(第一部)
頻出する文字列をより短い文字列に置き換えることで圧縮するので、ようはngramの計算が必要なんだと思います。 ngramを効率よく計算するにはどうしたらいいんでしょうかね。 とりあえずPythonでSuffixArrayを実装するのが意外と簡単にできたので、それを利用してngramを計算。1000文字ちょいのソースコードに対して、1000～2文字のngram頻度を計算し、その文字列を1文字に置き換えたときに縮む文字数をスコアとして、一番スコアの高い文字列を選択する、というコードが出来ました。
def makeSuffixArray(s):
result = range(len(s))
result.sort(lambda x,y: cmp(s[x:], s[y:]))
return result
def ngram(n, s, sa = None):
N = len(s)
if sa == None:
sa = makeSuffixArray(s)
prevStr = None
result = {}
for i in sa:
if i + n < N:
curStr = s[i : i + n + 1]
if prevStr == curStr:
result[prevStr] = result.get(prevStr, 1) + 1
prevStr = curStr
else:
prevStr = None
return result
from time import clock
t = clock()
maxScore = 0
maxStr = None
sa = makeSuffixArray(code)
for n in range(len(code) - 1, 1, -1):
ng = ngram(n, code, sa)
for s in ng:
score = (n - 1) * (ng[s] - 1) - 8
if score > maxScore:
maxScore = score
maxStr = s
print maxScore, maxStr
print clock() - t
大体2秒で結果が出ます。結果はもちろん「globals().__setitem__(」でした。引用符まで含まない方がスコアが高いんですね、ふむふむ。
できました。11秒で1000文字ちょいのワンライナーを578文字に圧縮することができました。
出力はこんな感じ。
'globals().__setitem__(' => 'z' (1401=>815)
')or z"' => 'q' (815=>728)
'(globals().get(p,0)' => 'Z' (728=>677)
'",lambda' => 'Y' (677=>638)
'qc",c+1)q' => 'X' (638=>609)
')for x in count())).next()' => 'W' (609=>587)
')or ifilter(bool,(' => 'V' (587=>573)
'Y:z"c",c+1qp",p' => 'U' (573=>562)
')%256X' => 'T' (562=>555)
'Y:zp,' => 'S' (555=>550)
'import ' => 'R' (550=>547)
'z"c",' => 'Q' (547=>546)
'z"t",' => 'P' (546=>545)
'1)q' => 'O' (545=>542)
置き換えて得になる文字列がありません
542
8.57972759108
コマンドライン引数から実行するBrainf*ckスクリプトを読み込むようにしたら576文字。updateを__setitem__に変えるとなんと547文字まで縮みました。 今回はじゃんけん2.0の教訓を生かして、空白文字やコメントを除去する作業をプログラムに任せたので、比較的見やすい「元のコード」をいじって、より小さくなるコードを探すことが出来るようになりました。
あ、スコアの計算式に間違いがあるせいで縮めた後また伸ばしてました。それを修正すると542文字まで縮みました。上の出力もなおした後のものにしました。
そろそろ飽きてきたのでコードの解説はなし(ぇ)
完成したBrainf*ckワンラインインタプリタはこちら
みどころ。 「>U+O<U-O+SZ+1T-SZ+255T」 これはBrainf*ckの>, <, +, -の定義です。 >U+O <U-O +SZ+1T -SZ+255T。美しい…。
class Compressor:
def __init__(self, s):
self.repl = []
self.target = s
available = list("|!#$%&()*+,-./:;<=>?@[]^_`{}~0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz")
import sets
for c in sets.Set(s):
if c in available:
available.remove(c)
self.available = available
def step(self):
N = len(self.target)
if len(self.available) == 1:
print "置き換える対象の文字が残っていません"
return True
c = self.available.pop()
maxScore = 0
maxStr = None
sa = makeSuffixArray(self.target)
for n in range(N - 1, 1, -1):
ng = ngram(n, self.target, sa)
for s in ng:
score = (n - 1) * (ng[s] - 1) - 2
if score > maxScore:
maxScore = score
maxStr = s
if maxStr == None:
print "置き換えて得になる文字列がありません"
return True
self.oldCode = self.getCode()
self.target = self.target.replace(maxStr, c)
self.repl.insert(0, c + maxStr)
print repr(maxStr), "=>", repr(c), "(%d=>%d)" % (len(self.oldCode), len(self.getCode()))
def getCode(self):
splitter = self.available[0]
repl = splitter.join(self.repl)
return "exec(reduce(lambda x,y:x.replace(y[0],y[1:]),'%s'.split('%s'),'%s'))" % (
repl, splitter, self.target)
from time import clock
t = clock()
c = Compressor(code)
while True:
if c.step():
break
# exec(c.getCode(), {})
# print
print len(c.getCode())
print clock() - t
