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つ。

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の配列の各データの区切りの,を

使用しなくて

すむため、さらなるデータ表現の効率化が見込めます。

1379Byte。約60%のサイズ。元のデータからは12%以下になりました。

既に出てきたデータと同じ部分を繰り返し情報におきかえる。

1つ前のデータの差分ごとにした数値配列にし、同じデータが

  連続した場合はエスケープ値の後を繰り返し数とすることで

  同値、もしくは等差数列の場合に圧縮します。

  さらに同じ値の連続は起こりやすいと考えられるため、差分が0の

  連続の場合は0をセットせず、直接エスケープ値の後に繰り返し

  数をセットし、繰り返しの差分が0以外の場合はその数値をセット

  した後にエスケープ値をセットし、その後に(繰り返し数 x -1)を

  セットする。

  ここでは-32をエスケープ値とし、-32自体を表現したい場合は

  -32の後に0を置く(繰り返し0はありえないため)

  例 [100,101,101,101,101]の場合

    [100,1,-32,3]

    まず先頭は０からの差分である１００、次に101-100の１がきて、

　その後差分０が３回続くため-32(エスケープ値)の後、繰り返しの３

　が入る。

  例 [101,102,103,104,105]の場合

    [101,1,-32,-3]

　まず先頭は０からの差分である１０1、次に102-101の１がきて、

　その後差分1が３回続くため-32(エスケープ値)の後、繰り返し数３

　x -1 の-3が入る。

上記対応により625Byte!! 元のデータからは6%以下。

この圧縮が有効に効いた理由は、元データに1分足の時刻データが含まれて

おり、時刻情報全体が等差数列になっていたためです。

それだったら最初の時刻だけ送れば後は自明という気もしますが、休日を

挟んだ場合など途中に欠落がある可能性があるため、それを考慮する必要が

ない利点があります。

上記をJavaScriptで実装したものを、num_converter.js として公開しました。

残念ながら少数には使えませんが、小数点以下の桁数を決めておいて、

圧縮前に整数化し、展開後に少数に戻せばいいと思います。