JSONデータの圧縮について
はじめに
HTTPのContent-Encoding: gzipにより、アプリ側が意識しなくても
Webサーバ、ブラウザ間で自動的に圧縮、伸張が行われるため、JSON
データの冗長性に対してそれほど気にしないと思います。
しかし、socket.ioの場合、圧縮はサポートされていないため、気兼ねなく
JSONを使うとデータサイズが大きくなりがちです。またsocket.ioを使う
ようなリアルタイムの頻繁なやりとりでの巨大なデータサイズは、ネットワーク
に対する影響も大きいものとなります。
そこで、チャートのような似たようなデータの固まりのJSONのサイズを小さく
する仕組みを考えました。
前提
まず元のデータはドル円の1分足のデータで下記のようなものです。

141本分の1分間のローソク足データに対して、 11901Byte!!
項目ごとの配列に変更
まずopen,closeなどの重複した項目名がが目に付きます。
そこで項目名を一度だけ出力するように、各項目ごとの配列に変更してみます。

6720Byte。これにより元のデータサイズの56%になりました。
配列の値を差分に変更
チャートの数値データは似たような値のため、配列の値を一つ前の値の差分を
格納してみます。
時間は1970 年 1 月 1 日 00:00:00 UTC からの経過ミリ秒に置き換えます。

2291Byte。1/3のサイズ。元のデータからは約20%になりました。
ただ、1フレームですむ狙いの1400Byte以下まではまだ削減する
必要があります。
さらなるデータサイズ縮小を狙って、圧縮アルゴリズムについて考察
してみます。
圧縮のアルゴリズムについて
一般的な可逆圧縮方法は大きく分類すると次の2つ。
- データを元よりも短い記号に置き換える(符号化)
- 既に出てきたデータと同じ部分を繰り返し情報におきかえる
データを元よりも短い記号に置き換える(符号化)
JSONの数値は各桁の数字を1Byteで表現しているため、1Byteで表現できる
256種類のうちたった10個しか使っていません。
0-9以外の印字可能なascii文字も使うことで、1Byteで95個の表現を使用できます。
95という数字は 00000000-01011111まで。各bitの組み合わせごとにascii
文字を一意に決定します。
今回の数値を表現するbyteのフォーマットは3種類あります。
共通事項として、先頭Bitはascciiでは使わないため必ず0
になり2Bit目が0の場合はそのByteで数値が終わり、1の場合
は続くByteも数値に含まれることを表わします。
先頭Byte(数値1つにつき出現回数 1回)
先頭Bit: 必ず0
2Bit目: 1Byteで表現できない場合(数値が-32〜31の範囲外) ON
3Bit目:
数値が-32〜31の場合
数値に+32したものを5bitで数値化(0〜63)
例 -32の場合 00000000 1の場合 00100001
数値が-32〜31の範囲外
3Bit目: 必ず0
4Bit目: 数値がマイナスの場合は1、0以上の場合は0
5Bit目以降:
10bit以上で5で割れるbit数になるよう先頭を0でpaddingさせる。
中間Byte(数値1つにつき出現回数0〜複数回)
先頭Bit: 必ず0
2Bit目: 必ず1
3Bit目: 必ず0
4Bit目以降:
前のByteのbit並びの続き
最終Byte(0〜1回)
先頭Bit: 必ず0
2Bit目: 必ず0
3Bit目以降:
前のByteのbit並びの続き
例
-33の場合 01010000 00100001
1024の場合 01000001 01000000 00000000
さらに上記の符号化により、JSONの配列の各データの区切りの,を
使用しなくて
すむため、さらなるデータ表現の効率化が見込めます。

1379Byte。約60%のサイズ。元のデータからは12%以下になりました。
既に出てきたデータと同じ部分を繰り返し情報におきかえる。
1つ前のデータの差分ごとにした数値配列にし、同じデータが
連続した場合はエスケープ値の後を繰り返し数とすることで
同値、もしくは等差数列の場合に圧縮します。
さらに同じ値の連続は起こりやすいと考えられるため、差分が0の
連続の場合は0をセットせず、直接エスケープ値の後に繰り返し
数をセットし、繰り返しの差分が0以外の場合はその数値をセット
した後にエスケープ値をセットし、その後に(繰り返し数 x -1)を
セットする。
ここでは-32をエスケープ値とし、-32自体を表現したい場合は
-32の後に0を置く(繰り返し0はありえないため)
例 [100,101,101,101,101]の場合
[100,1,-32,3]
まず先頭は0からの差分である100、次に101-100の1がきて、
その後差分0が3回続くため-32(エスケープ値)の後、繰り返しの3
が入る。
例 [101,102,103,104,105]の場合
[101,1,-32,-3]
まず先頭は0からの差分である101、次に102-101の1がきて、
その後差分1が3回続くため-32(エスケープ値)の後、繰り返し数3
x -1 の-3が入る。

上記対応により625Byte!! 元のデータからは6%以下。
この圧縮が有効に効いた理由は、元データに1分足の時刻データが含まれて
おり、時刻情報全体が等差数列になっていたためです。
それだったら最初の時刻だけ送れば後は自明という気もしますが、休日を
挟んだ場合など途中に欠落がある可能性があるため、それを考慮する必要が
ない利点があります。
上記をJavaScriptで実装したものを、num_converter.js として公開しました。
残念ながら少数には使えませんが、小数点以下の桁数を決めておいて、
圧縮前に整数化し、展開後に少数に戻せばいいと思います。
| 固定リンク
| コメント (0)
| トラックバック (0)
最近のコメント