ポケモンカードのデッキを圧縮する
バトルコンプレッサーじゃないよ！
はじまり
先日、職場の若者の基本情報の試験勉強につきあっていて「ハフマン符号ってなんですか？」って聞かれて焦った。 ひと通り説明したあとで、なにか解説してる本がないかなと思って探してみたら「高速文字列解析の世界」を発掘した。
ハフマン符号はp.20にある。まあそれは良い。 その隣のページの「表2.2 正整数に対する各種符号による比較」というのがあって、へー Unaryという言葉があるんだなあ、本はちゃんと読むべきだなあ、と思ったのであった。
ポケモンカードのデッキのための符号
そういうわけで、なにかの符号を考える練習することに。まあ、例によってポケカを題材にするんだけど。 とくにメモリとかストレージで問題があるわけではないが、ポケモンカードのデッキを小さめのデータで表現してみる。
デッキ
デッキは60枚のカードで構成される。同じ名前のカードは4枚まで、基本エネルギーは何枚でも入れることができる。
これは公式サイトのデッキ構築サイトの画面。
カードには正の整数のIDが振られている。このデッキをカードのIDとその枚数の配列で表現するとこんな感じ。
% irb --simple-prompt >> it = [[38974,4],[39449,3],[39763,2],[37259,1],[39217,2],[40047,1],[40048,1],[39 283,3],[38685,3],[39285,3],[39220,2],[39193,4],[39221,3],[39961,3],[37755,2],[3984 5,2],[39191,1],[39231,3],[39232,2],[39732,2],[39334,1],[38826,3],[37745,9]] => [[38974, 4], [39449, 3], [39763, 2], [37259, 1], [39217, 2], [40047, 1], [... >> pp it [[38974, 4], [39449, 3], [39763, 2], [37259, 1], [39217, 2], [40047, 1], [40048, 1], [39283, 3], [38685, 3], [39285, 3], [39220, 2], [39193, 4], [39221, 3], [39961, 3], [37755, 2], [39845, 2], [39191, 1], [39231, 3], [39232, 2], [39732, 2], [39334, 1], [38826, 3], [37745, 9]]
カードのIDは16bit整数のことが多く、枚数は8bitに収まる。
JSONなどの文字列で表現すると231文字だ。
>> it.to_json.size
=> 231
Marshal.dumpだと188byte。
>> Marshal.dump(it).size => 188
配列の入れ子にする必要はないのでflattenすると小さくなる。
>> Marshal.dump(it.flatten).size => 142
並べ替えてみる
デッキはどんなカードがあるかに意味があって順序には意味がない。並べ替えてみるとこうなる。
>> sorted = it.sort_by {|x| x[0]}
=> [[37259, 1], [37745, 9], [37755, 2], [38685, 3], [38826, 3], [38974, 4], [...
>> pp sorted
[[37259, 1],
[37745, 9],
[37755, 2],
[38685, 3],
[38826, 3],
[38974, 4],
[39191, 1],
[39193, 4],
[39217, 2],
[39220, 2],
[39221, 3],
[39231, 3],
[39232, 2],
[39283, 3],
[39285, 3],
[39334, 1],
[39449, 3],
[39732, 2],
[39763, 2],
[39845, 2],
[39961, 3],
[40047, 1],
[40048, 1]]
次に隣り合ったカードのIDの差を出してみる。並べ替えて差で表現するのは定番のネタである。
>> pp sorted.sort_by {|x| x[0]}.each_cons(2).map {|ab| [ab[1][0] - ab[0][0], ab[1]
[1]]}
[[486, 9],
[10, 2],
[930, 3],
[141, 3],
[148, 4],
[217, 1],
[2, 4],
[24, 2],
[3, 2],
[1, 3],
[10, 3],
[1, 2],
[51, 3],
[2, 3],
[49, 1],
[115, 3],
[283, 2],
[31, 2],
[82, 2],
[116, 3],
[86, 1],
[1, 1]]
カードID同士の差は8bitの範囲で収まることが多く、たまに越えることがあるようだ。 先頭は0からの差、と考えて追加してみる。
>> diff = [sorted[0]] + sorted.sort_by {|x| x[0]}.each_cons(2).map {|ab| [ab[1][0] - ab[0][0], ab[1][1]]} => [[37259, 1], [486, 9], [10, 2], [930, 3], [141, 3], [148, 4], [217, 1], [2...
これをflattenしてMarshalしてみよう。
>> Marshal.dump(diff.flatten).size => 107
おー。減ったぞ。Marshalかしこい。
Marshalは型情報を持っていて損しているはず。packで表現してみるか。 これを実験する時に見つけたんだけど w （BER圧縮整数）という書式があるのね。これ使ってみよう。
BER圧縮整数
1バイトあたり7ビットを使用して必要最小限のバイト数で任意サイズの 0以上の整数を表す数値表現。各バイトの最上位ビットはデータの最後を除いて必ず1が立っている(つまり最上位ビットはどこまでデータがあるかを示している)。 ISO/IEC 8825-1:1995 : Information technology−ASN.1 encoding rules : Specification of Basic Encoding Rules(BER) に定められる整数の符号化方法。
>> diff.flatten.pack("w*").size => 54
54バイト！！半分くらいに小さくなった！
ところで、BER圧縮整数は1ビットを使ってデータの終端を示している。このため、先頭の37259は次のように3バイトになる。
>> [37259].pack('w') => "\x82\xA3\v" >> [37259].pack('w').unpack('C*') => [130, 163, 11]
この1ビットのフラグを別の場所に避けてあげられないだろうか...。
ポケカに依存した圧縮
デッキに入るカードの枚数は60枚。つまり6bitで収まるはず。あまった2ビットでデータ（ここではカードID、あるいはその差分ね）の長さを表現できるのではないか！？ BERが8ビット目を使っているところを、カードの枚数の使ってない2ビットに移すような感じ。 データの長さは0はあり得ないので、1オリジンと考える。上位の2ビットが0ならデータの長さは1バイト、3なら4バイトということになる。
この作戦でpackするpack_cardというメソッドを作って実験。（正の整数をunsinged charの配列に変換するbytesというメソッドも作ったが何かを使うと一発でもとまるのではないだろうか）
?> def pack_card(card) ?> card, n = card ?> ary = bytes(card) ?> ?> [((ary.size - 1) << 6) + n, *ary].pack("C*") >> end => :pack_card >> ?> def bytes(n) ?> q, r = n.divmod(256) ?> return [r] if q == 0 ?> bytes(q) + [r] >> end => :bytes >> diff.map {|x| pack_card(x)}.join => "A\x91\x8BI\x01\xE6\x02\nC\x03\xA2\x03\x8D\x04\x94\x01\xD9\x04\x02\x02\x18\x02\x03\x03\x01\x03\n\x02\x01\x033\x03\x02\x011\x03sB\x01\e\x02\x1F\x02R\x03t\x01V\x01\x01" >> diff.map {|x| pack_card(x)}.join.size => 50
50バイト！
ちなみにunpackしたら元にもどった。よかった。
def unpack_deck(bin) result = [] ary = bin.unpack("C*") last = 0 while c = ary.shift sz = c[6..7] + 1 n = 0 sz.times do n = n * 256 + ary.shift end last += n result << [last, c[0..5]] end result end
まとめ
（ビット操作等のめんどうなことをやらず、）簡単に書ける範囲で練習したので、自己肯定感がさらに高まった。
そして、本はちゃんと読んだほうがよい。
さいごに
m_seki is creating code.もはじめました。
