@m_seki の

I like ruby tooから引っ越し

ポケモンカードのデッキを圧縮する話

ポケモンカードのデッキを圧縮する

バトルコンプレッサーじゃないよ!

はじまり

先日、職場の若者の基本情報の試験勉強につきあっていて「ハフマン符号ってなんですか?」って聞かれて焦った。 ひと通り説明したあとで、なにか解説してる本がないかなと思って探してみたら「高速文字列解析の世界」を発掘した。

ハフマン符号はp.20にある。まあそれは良い。 その隣のページの「表2.2 正整数に対する各種符号による比較」というのがあって、へー Unaryという言葉があるんだなあ、本はちゃんと読むべきだなあ、と思ったのであった。

ポケモンカードのデッキのための符号

そういうわけで、なにかの符号を考える練習することに。まあ、例によってポケカを題材にするんだけど。 とくにメモリとかストレージで問題があるわけではないが、ポケモンカードのデッキを小さめのデータで表現してみる。

デッキ

デッキは60枚のカードで構成される。同じ名前のカードは4枚まで、基本エネルギーは何枚でも入れることができる。

https://www.pokemon-card.com/deck/deckView.php/deckID/My2R2X-5EZvYk-ySpMMS.png

これは公式サイトのデッキ構築サイトの画面。

www.pokemon-card.com

カードには正の整数の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.もはじめました。

LightroomとClassic

Lightroomに移行した

セコンさんが那須塩原に引っ越してきたので、思い出したことがある。写真の現像環境をLightroom ClassicからLightroomに移行したんだった。 きっかけは次の記事。

secon.dev

前からLightroomへの移行を迷ってたんだけど、先人を真似することにした。

以下、自分の手順。特に数ヶ月に一回しかやらない作業は忘れてしまうので自分用のメモ。

ワークフロー(車中。カメラ→iPad

自動車生活なので、クルマでロケハン、撮影、ピントのチェックをやってしまう。輝度はあとで誤魔化せるけど、他の失敗は取り返しがつかないので、その場で確認できると嬉しい。

  1. カメラのSDカードをiPad Proに読み込ませる。無線でもできるけどSDカード経由の方が速くて安定してる。読み込み先は「写真.app」。転送が終わったらSDカードからは消してしまう。
  2. 軽くチェック。明らかなボツはこの時点で削除する
  3. このときInstagramにあげることもある。

iPadの写真はiCloudに保存しないようにしてある。ここまで、クラウドとの同期なし。

ワークフロー(帰宅後。写真.app→Lightroom

以下は帰宅後にやること。

  1. もう一度確認して、没にする写真を選んで削除。
  2. Lightroom.app で選択的に画像追加
  3. 現像。

現像はiPadで終わらせることが多くなってきた。たまに気分でMacで現像することもある。

ワークフロー(数ヶ月に一度。クラウド側の整理)

自分のプランはフォトプラン(20GB)。Psも使うのでフォトプランが良いのだが、ストレージが小さいので、定期的に整理する必要がある。 1TBのプランも用意されているのは知っているが、広ければ広いで没写真が蓄えられるだけどろう、と想像して、20GBのまま使うことにした。

自分は直近の写真は現像するけど、過去の写真は眺めるだけのことが多い。 そこで、Lightroom Classicを使ってクラウド上の写真を同期してローカルストレージに保存することにした。

  1. Lightroom Classicを起動。クラウド上の写真を同期する。
  2. Lightroomクラウド上の古い数ヶ月分を削除。この時、写真を見てしまうと終わらなくなるので機械的に削除する。

Clasicでローカルに持ってきたのち、クラウド上の写真を削除してもローカルの写真は残る(ようだ)。

1TBを整理するよりも20GBを整理する方が簡単だと信じてる。でも、1TBあったらそもそも整理する必要がなくなるんだろうか..。それはそれで魅力的だ。

まとめ

没画像をどうやって整理するかの話になってしまった。整理をサボると収拾つかなくなっちゃうから仕方なくやってるけど、無限にストレージあればやらずに済むのになー

Discordの音楽再生botの話 #FM719

Discordの音楽再生botの話 #FM719

はてブロproにしてからほとんど記事を書いてないということを、請求書を見て思い出しました。とほほ。 半年ぶりに書きます。discordrbのvoice botをスムーズにした話。テックブログ風!

DiscordにBGMいれたい

先日、とある配信のためにDiscordでBGMを流す必要がありました。

方式の候補は二つ

  • 音声入力にミキシングする
  • 音楽再生サービスのbotを使う

ミキシングする

ミキシングするやつは半年前に効果音で使って実績がある。 マイクからの音声とMacの中の音源を混ぜるやつ。

druby.hatenablog.com

これ、効果音のときは気づかなかったんだけど、連続する音楽だとうまくいかない。 アプリ側が持っているノイズ抑制の機能のせいなのか、途切れ途切れになってしまう。

音楽再生サービスのbotを使う→作る

じゃあ、bot使うか、と思って音楽再生サービスのbotを調べたら軒並みサービス停止されてました。*1 これはこまった。

よく考えたら再生したいのは自分のmp3なんだから自分でbot作ればいいんだよな。 じゃあ、作るか。

音声が途切れちゃう

まず、discordrbというgemを読みました。名前がdrbっぽいね。

サンプルに再生botがついていて便利。

https://github.com/shardlab/discordrb/blob/main/examples/voice_send.rb

ちょっと修正して実験。確かにmp3が再生されるけどぶつぶつ途切れてしまう。なんだこれは。 流行りの技術系ブログにも似たような質問に答えがあって「帯域のせい」とのことでした。(ほんとか?)

調べていると、fredboatっていうサービスはまだ生きていて、youtubeの曲を再生させることができました*2。 でもね、このbotは途切れないんですよ。なんだこれ。ということは帯域とかAPIのせいじゃなくてbotの実装がおかしいんじゃないの? これは直すしかない。

処理時間に注目してる

discordrbの音声を再生する部分はここ。play_internalっていうのが再生ループ。

https://github.com/shardlab/discordrb/blob/main/lib/discordrb/voice/voice_bot.rb

Discordは20msecごとにudpでデータを送る約束になってるように見える(斜め読み)。 できるだけ20msecに近い間隔で送信したいと思っているんだろうな、と想像して読んでみる。

自分とはリズムが違うコードなので、読むのしんどい。まずはチラ見で。

あ。Timeのnsec部分だけを使って計算してる...。これじゃ秒跨ぎ問題(0:00:00.999と0:00:01.001のnsecどうしを比べたら負になる問題ね)が起きるだろ!と思って修正したけど特に効果なし。 よく考えたら20msec以内の処理なんだから、秒を跨ぐところに処理がくる頻度は低いよな..。 もっと本格的にダメなんだな。

チラ見じゃなくて、ちゃんと読むか...。

あーー。これ、ループの内側で送信の前処理にかかる時間を計測して、送信後に20msecから前処理の時間分減らした時間でsleepしてる。ループの内側が20msecにしようとしてるんだな。ダメじゃん。これ職場やtoRubyタイマーでも似たようなの見たことあるぞ。ループごとに隙間あくし、遅延も累積する。*3

かかった処理時間に注目して、ループの内側が20msecに調整するのだ、という作戦かな。

送信時刻に注目する

定番のバグなのでささっと直しました。

  • ループの開始前に起点になる時刻を決める。
  • 起点の時刻 + 20msec * n回目、でそのループでの送信したい時刻を計算。
  • 送信したい時刻と現在時刻の差だけsleepする。すぎてたらsleepしない。
  • udbで送信。

送信する時刻を20msecおきにしたいのだ、という作戦です。

sleepのための計算とsleep解除後からudb送信までに僅かな処理があり遅延がある、とも言える。しかしどのループでもだいたい同じくらいの遅延になるので、再生に隙間は現れにくい。

gist925d73ba7aab871ad71597d579864f44

というわけで、ほぼ20msecおきに送信することができるようになって、再生もとてもスムーズになりました。

パッチでフィードバックしたいと思ったんだけど、元のコードの気持ちが読み取れきれず、パッチにできませんでした。とりあえずサンプルコードを送りました。

もし他のvoiceなbotで音声が途切れちゃうのであれば、どんなふうに20msecを刻んでいるのか調べてみるといいかもね。

おまけ

botのパーミションの設定とかはここを真似したよ!

Discordでローカルのmp3をボイチャで流す - ておくれるままに...

BGMのためにこれを読んだよ!

作りながら覚える 3日で作曲入門

作りながら覚える 3日で作曲入門

Amazon

*1:youtubesoundcloudの楽曲を再生するからかなあ

*2:soundcloudに対応しているはずなんだが失敗した

*3:なお調整は10回に一度くらい行われている。なんでそうしたんだろ。