MessagePack の不満と、別の案

これは何？

MessagePack を使っていて、こうだったらいいのに、と思ったことがあったのでそれを記載する。

MessagePack の不満

対応できない型と値

10進浮動小数点数、半精度浮動小数点数、有理数、なんかがない。
64bit を超える巨大な数も対応できない。

JSON なら 1e999999 だって 1267650600228229401496703205376 だって書けるのに。

サイズ的にもったいない

key-value-pair の配列があって、全要素の key が同じってのはわりとよくあるとおもうんだけど、その場合でも全部の key を書かないといけないのが不満。

これは JSON も同様。

長さ制限

必要な場面はなかなかないとは思うけれど、$2^{32}$ を超える長さの配列とかがないのが残念。

極稀だけど 数GB の JSON の話とか耳にするので、ない話ではないんだと思う。

仕様案

すぐに実装しようという気分ではないんだけど、MessagePack を参考にしつつ思いつくままに書いておく。

方針

型は nil / 真偽 / 数値 / 複素数 / 行列 / 配列 / key-value-pair (以下KVP）/ タイムスタンプ。
数値には、非数と無限も含まれる。

JSON のように、数値が整数型 かどうかを知る方法はないことにする。整数型の値でも、浮動小数点方式で保存したほうがバイト数が少なくなるから、とかいう理由で浮動小数点方式で保存しても良いことにする。

型を決めたければスキーマ作れ。という態度。

メッセージパックを真似て、拡張型もあったほうがいいのかな。

仕様案

バイナリとしては、メッセージパックを真似て
　1バイトの識別子 + データ部
とする。データ部はないこともある。

識別子一覧

識別子の値を決める段階にいないんで、個数だけ。

意味	カテゴリ	識別子の個数	補足
ゼロ	実数	1	データ部なし
短い整数	実数	30個ぐらい	データ部なし
固定長整数	実数	8個	u8, u16, u32, u64, i8, i16, i32, i64
長い整数	実数	1
2進固定長浮動小数点数	実数	3	binary16, binary32, binary64
2進可変長浮動小数点数	実数	1
10進可変長浮動小数点数	実数	1
有理数	実数	1	整数値である実数のペア
複素数	数学	1	実数のペア
行列	数学・コンテナ	1
bool	論理	2	データ部なし
nil	nil	1	データ部なし
バイナリ	文字列?	16個ぐらい	16個ぐらいのうち一個だけ可変長
utf8 文字列	文字列	16個ぐらい	16個ぐらいのうち一個だけ可変長
英数字 文字列	文字列	16個ぐらい	base64みたいにして縮める
配列	コンテナ	16個ぐらい	16個ぐらいのうち一個だけ可変長
KVP	コンテナ	16個ぐらい	16個ぐらいのうち一個だけ可変長
テーブル	コンテナ	16個ぐらい	全要素でキーが同じであるような配列
タイムスタンプ	その他	4個ぐらい？

これで 200個に満たないので、なんとかなるんだろう。

適当に説明

文字列とかは、可変長と固定長が混在。

例えば識別子 0x70〜0x7f が文字列として。

1文字の文字列のために長さ情報をつけるのはもったいないので、0x70〜0x7e は、0バイトから14バイトまでの固定長。長さ情報は識別子に埋まっているので識別子の直後にデータが来る。
0x7f だけは可変長で、長さ情報がつき。長さに続いてバイト列が並んでいる。みたいにする。
MessagePack と似た方針だけど、下表のとおり違う

	MessagePack	この案
識別子	可変長文字列だけで3個	1個
長さの制限	$2^{32}-1$ 件を超えられない	書式上は制限がない

識別子一個で無制限の長さを扱うための仕組みは下記。

長さ

可変長のデータには、長さがついている。
長さを示すバイト列も可変長。
MSB が 0 だと終端で、MSB が 1 だと「続きがあるよ」という意味。

たとえば、長さが 0x10 なら、 0x10 とすればよい。
長さが 0x4321 なら、0x4321 を 7bit ずつに分けて [0x1, 0x6, 0x21] 。
末尾以外は MSB を立てて [0x81, 0x86, 0x21] となる。このバイト列で長さを表現する。

長い整数・可変長 utf-8文字列・可変長 バイト列

先頭に長さがあり、あとはバイト列。
整数は 普通に 2の補数表現で。

2進 可変長浮動小数点数

中身は整数２つ。それぞれ e と f とする。ただし、f はゼロでないこと。
デコード側のロジックで書くと：
$1 ≦ \frac{\left| f　\right|}{2^{n}} < 2$ となるような 整数 n をもとめたうえで、
e と f の組が表す値は $2^{e-n} \times f$ とする。

e=-4, f=5 なら、n=2 となり、値は 0.078125 となる。

非正規化数・無限・非数はない。そういうものが必要なら固定長浮動小数点数を使う。

10進 可変長浮動小数点数

2進 可変長浮動小数点数 とほぼ同じ。10進数にするだけ。

整数２つ。それぞれ e と f とする。ただし、f はゼロでないこと。
$1 ≦ \frac{\left| f　\right|}{10^{n}} < 10$ となるような 整数 n をもとめたうえで、
e と f の組が表す値は $10^{e-n} \times f$ とする。

e=-4, f=5 なら、n=0 となり、値は 0.0005 となる。

英数字 文字列

英数字・下線・ハイフン（ハイフンじゃなくて空白がいい？） の 64種類以外の文字がない場合で4文字以上ならこちらを使う。

KVP のキーをこれでちょっとでも小さくするという作戦。
エンコード時だるいけど。

base64 方式で、4文字を3バイトにする。
ちょっとお得。たとえば、"profile_image_url" (17文字) なら 4バイトお得。

そんなにサイズ気にならないなら、無くてもいい。

配列

要素数分のオブジェクトが普通に並ぶ

KVP

要素数×2個 のオブジェクトが普通に並ぶ

テーブル

JSON で書いたら

json

[
  { "foobar": 8, "bazhoge": 9 },
  { "foobar": 2, "bazhoge": 4 },
  { "foobar": 6, "bazhoge": 4 },
  { "foobar": 0, "bazhoge": 8 },
  { "foobar": 2, "bazhoge": 8 }
]

みたいになるやつ。キー名同じなんだから何度も書いたらもったいない。これを

• キーは foobar と bazhoge。
• 値は 8, 9, 2, 4, 6, 4, 0, 8, 2, 8
  という形にするとだいぶ小さくなってお得。

データ部としては、キーの個数・キーのリスト・値の個数・値のリスト かな。

行列と複素数

欲しい人多いんじゃないの？ と思って書いておいた。

複素数は実数のペア。

行列の中身は、行数・桁数・値のリスト。値のリストに入るのは複素数または実数かな。
ruby なんかは文字列要素の行列作れたりするけど対応しなくていいと思う。

非数・無限・-0.0

可変長の浮動小数点数には非数も無限もない。整数にも有理数にもない。
格納する際は、固定長の浮動小数点数を使うしかない。バイト数としてお得なので、半精度を使うのが良い。
識別子＋データ部で 3バイト。

+0.0 は 0 なので、整数のゼロ（つまり 1バイト）を使うのが良い。
-0.0 は 整数のゼロしてしまうと +0.0 と区別できなくなるので、必要なら 半精度 を使うのがいい。

ということで。

実装する予定は全然ないんだけど、書いておいた。
実装したい人がいたらコメントなど頂ければうれしいし、相談にも乗るかも（乗らないかも）。