« JavaScriptをminifyしてgzipしてS3へのアクセスにする | トップページ | Socket.IO用フレームワーク socket.io-reqev »

2013年9月13日 (金)

JSONデータの圧縮について

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


前提
まず元のデータはドル円の1分足のデータで下記のようなものです。
20130913_215757
141本分の1分間のローソク足データに対して、 11901Byte!!


項目ごとの配列に変更
まずopen,closeなどの重複した項目名がが目に付きます。
そこで項目名を一度だけ出力するように、各項目ごとの配列に変更してみます。
20130913_215904
6720Byte。これにより元のデータサイズの56%になりました。


配列の値を差分に変更
チャートの数値データは似たような値のため、配列の値を一つ前の値の差分を
格納してみます。
時間は1970 年 1 月 1 日 00:00:00 UTC からの経過ミリ秒に置き換えます。
20130913_215929
2291Byte。1/3のサイズ。元のデータからは約20%になりました。
ただ、1フレームですむ狙いの1400Byte以下まではまだ削減する
必要があります。
さらなるデータサイズ縮小を狙って、圧縮アルゴリズムについて考察
してみます。

圧縮のアルゴリズムについて
一般的な可逆圧縮方法は大きく分類すると次の2つ。
  1. データを元よりも短い記号に置き換える(符号化)
  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の配列の各データの区切りの,を
使用しなくて
すむため、さらなるデータ表現の効率化が見込めます。
20130913_220008
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が入る。
20130913_220030
上記対応により625Byte!! 元のデータからは6%以下。
この圧縮が有効に効いた理由は、元データに1分足の時刻データが含まれて
おり、時刻情報全体が等差数列になっていたためです。
それだったら最初の時刻だけ送れば後は自明という気もしますが、休日を
挟んだ場合など途中に欠落がある可能性があるため、それを考慮する必要が
ない利点があります。
上記をJavaScriptで実装したものを、num_converter.js として公開しました。
残念ながら少数には使えませんが、小数点以下の桁数を決めておいて、
圧縮前に整数化し、展開後に少数に戻せばいいと思います。

|

« JavaScriptをminifyしてgzipしてS3へのアクセスにする | トップページ | Socket.IO用フレームワーク socket.io-reqev »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/68673/58186597

この記事へのトラックバック一覧です: JSONデータの圧縮について:

« JavaScriptをminifyしてgzipしてS3へのアクセスにする | トップページ | Socket.IO用フレームワーク socket.io-reqev »