ARJSONの紹介 - JSONエンコーディングの最適化

原文: ARJSON

ARJSON

ARJSON はビットレベルの最適化を活用して、MessagePackやCBORなどの他の自己完結型 JSON エンコーディング/圧縮アルゴリズムよりも効率的にデータを圧縮しながら、高速に JSON をエンコードします。

ARJSON が他のすべてのエンコーディングアルゴリズムを上回る理由

MessagePack は既存の自己完結型 JSON シリアライゼーションフォーマットの中で最小のエンコードデータサイズを生成します。しかし、ARJSON はランダムデータの 90%のケースで MessagePack を上回り、残りの 10%でもほぼ同等のサイズを実現します。さらに重要なのは、繰り返しパターンや重複する値を持つ構造化データでは、ARJSON は MessagePack を大幅に上回り、最大約 95%の圧縮率向上（サイズが 20 分の 1）を達成します。

現状の技術をこれほど大幅に上回ることがどうして可能なのでしょうか？

• 従来のバイトレベルエンコーディングに対するビットレベルの最適化
  MessagePack などのシリアライゼーションアルゴリズムはバイトレベルで最適化されており、エンコードされたデータ全体に未使用のビットが散在していることがよくあります。1 バイトは 8 ビットで構成されるため、データは通常、標準的なメモリ構造に合わせてバイトにパッキングされます。対照的に、ARJSON は可変長データユニットを持つビットレベルの最適化を活用し、すべてのビットが効率的に使用され、無駄なスペースが残らないようにします。
• 圧縮を強化するためのカラム構造の再編成
  ARJSON は JSON データをスキャンする際に、動的にカラム構造に再編成します。現代のデータベースは同じフィールドの値を一緒に格納することで高いパフォーマンスを実現しており、これは自然に類似データのシーケンスをもたらします。この構造的な整列により、データサイズがより均一で予測可能になり、冗長性が高まり、隣接する値間の違いが最小化され、最終的に優れた圧縮効率につながります。
• 連続的で繰り返しデータの効率的な保存のためのデルタパッキング
  ARJSON はカラム構造を活用して、連続する値の差分をエンコードし、繰り返しシーケンスを効率的にパックします。タイムスタンプ、カウンター、構造化レコードなど、意味のあるデータは自然にパターンを形成するため、デルタパッキングはこれらの繰り返しを最大限に活用し、ストレージを大幅に削減し、圧縮効率を向上させます。
• シンプル、決定論的、メタデータ効率
  高度な圧縮機能にもかかわらず、ARJSON はシンプルな決定論的原則に基づいています。たった 1 回のスキャンで、複数のパスや複雑なヒューリスティックを必要とせずに、ビットレベルの最適化、カラム再編成、デルタパッキングを動的に適用します。決定論的な順序により不必要なメタデータの必要性が排除され、ストレージのオーバーヘッドがさらに削減され、コンパクトで合理化されたエンコーディングプロセスが確保されます。
• 直接データ抽出と ZK 互換性
  ARJSON の構造化されたエンコーディングにより、データは完全なデコードなしに直接アクセスでき、オンザフライ処理に非常に効率的です。これは、算術演算のみが許可されるゼロ知識証明回路（ZK 回路）にとって特に重要で、コストの高いパースが不要になります。さらに、ARJSON のコンパクトで予測可能なフォーマットにより EVM アセンブリレベルの最適化が可能になり、ブロックチェーン環境でのガスコストを削減し、実行効率を向上させます。

ビットレベルの最適化

LEB128はバイトレベルで最適化された整数エンコーディング方式で、7 ビットチャンクを使用してバイトごとに 128 進数を表現します。最上位ビット（MSB）は継続フラグとして機能し、数値を完全にエンコードするために追加のバイトが必要かどうかを示します。これにより、可変長整数を効率的に格納し、無駄なスペースを最小限に抑えることができます。

例えば、

• 3 : 00000011
• 120 : 01111000
• 150 : 10010110 00000001 = 22 (00010110) + 128 * 10 ** 1 (00000001)

しかし、LEB128 の小さな数値はビットを無駄にします。3 は 2 ビット（11）しか必要としませんが、LEB128 では 8 ビットを消費します。

ARJSON は、数値エンコーディングスキームを指定する 2 ビットフラグに続いて、数値に必要な最小ビット表現を導入することで、無駄なビットを排除します：

• 00 : 2 ビット整数
• 01 : 3 ビット整数
• 10 : 4 ビット整数
• 11 : LEB128

例えば、3は0011（フラグ：00、整数：11）として格納され、4 ビットしか使用しません—LEB128 と比較して 50%の削減です。

1,000 個の数値を格納する場合、ARJSON は数値あたり 4 ビットを節約し、5,000 ビット（500 バイト）のストレージを節約します—これは圧縮効率の大幅な向上です。

さらに、ARJSON はコンテキストに基づいて整数エンコーディングを適応させ、3 つの最適化されたスキームを使用します：

• Short

  • 00 : 2 ビット整数
  • 01 : 3 ビット整数
  • 10 : 4 ビット整数
  • 11 : LEB128

• Uint

  • 00 : 3 ビット整数
  • 01 : 4 ビット整数
  • 10 : 6 ビット整数
  • 11 : LEB128

• LEB128

  • フラグ不要

この適応的なアプローチにより、高速なエンコードとデコードを維持しながら、ストレージのオーバーヘッドを最小限に抑えることができます。

既知の最大長を持つ整数の場合、ARJSON は追加のフラグを必要としません。例えば、ARJSON は 8 つの値タイプのみを定義するため、各タイプは 3 ビット以内で表現できます。このような場合、2 ビットフラグは省略され、代わりに 3 ビット整数エンコーディングが使用されます。

これにより、数値あたり 2 ビットが節約され、LEB128 の最小 8 ビット表現と比較して合計 5 ビットの削減につながります。

さらに、ARJSON はデータを 1 回スキャンし、決定論的な順序でカラム形式に再構成します。このアプローチでは、ビット位置が各数値が表す内容を固有に定義するため、明示的なマーカーやメタデータが不要になります。

カラム再構築

ARJSON は JSON データを整数表現に変換し、スキャン中にカラムベースのチャンクに整理します。エンコードされたデータは 13 のグループに分けられ、関連する値がまとめてパックされます。パッキングの順序は重要であり、前のグループはその後のグループのメタデータとして機能します。

1. 最初のビット

最初のビットは、データが空の配列（[]）やオブジェクト（{}）を含むプリミティブ型であるか、または空でない配列やオブジェクトであるかを分類します。プリミティブ型は追加の構造メタデータを必要としないため、個別の最適化されたエンコーディングパスに従い、多くの場合 1 バイトしか必要としません。

• 0 : 空でない構造化オブジェクト
• 1 : プリミティブ値または空の配列または空のオブジェクト

2. 値の数

最初のビットが0の場合、次のビットは JSON の値の数（short）を表します。

3. 値フラグ

ARJSON は、値をキーに、キーを親オブジェクトにリンクする構造マップを構築し、オブジェクトと配列もマークします。例えば、{ a: 1, b: 2, c: [3, 4] }では、まずオブジェクト{}を発見し、次にa => 1 => b => 2 => c => [] => 3 => 4を巡ります。これによりキーマップ[ -1, 0, 0, 0, 3 ]と値マップ[ 1, 2, 4, 4 ]が生成されます。キーマップは[ "{}", "a", "b", "c", "[]" ]に、値マップは[ 1, 2, 4, 4 ]にそれぞれ対応します。差が 4 未満の場合、値マップはデルタに変換され、通常は小さな整数になりビットを節約します。つまり[ 1, 2, 4, 4 ]は[ 1, 1, 2, 0 ]になります。デルタが減少する場合、負のシフトを示すために 4 のオフセットが追加されます。

• [ 1, 2, 4, 4 ] => [ 1, 1, 2, 0 ]
• [ 1, 2, 4, 2 ] => [ 1, 1, 2, -2 ] => [ 1, 1, 2, 6 ]
• [ 1, 2, 4, 10 ] => [ 1, 1, 2, 10 ]

値フラグは対応する項目がデルタ（1）か非デルタ（0）かを指定する 1 ビットフラグです。

• [ 1, 1, 2, 0 ] => 1111（すべてデルタ）
• [ 1, 1, 2, 6 ] => 1111（すべてデルタ）
• [ 1, 1, 2, 10 ] => 1110（10を除いてすべてデルタ）

デルタエンコードされた値について、ARJSON は数値あたり 3 ビットのみを使用し（範囲 0〜8）、非デルタ値と比較して複数ビットを節約します。

4. 値リンク

値リンクは値マップ（[ 1, 1, 2, 0 ]）を表し、各整数のビット長は値マップとキーマップを組み合わせることで決定論的に決定されます。例えば、キーマップ[ -1(0), 0(1), 0(2), 0(3), 3(4) ]と値マップ[ 1(v), 2(v), 4(v), 4(v) ]が与えられた場合、スキャン順序を保持すると[ -1(0), 0(1), 1(v), 0(2), 2(v), 0(3), 3(4), 4(v), 4(v) ]になります。キーインデックスは常に増分するため、1(v)は前のインデックスのみを参照でき、2 ビットだけでエンコードしても安全です。ただし、0はビット増分のために予約されているため、ARJSON はエンコード前に非デルタ値を 1 増加させるので、[ 1, 2, 4, 4 ]は[ 2, 3, 5, 5 ]になり、2(v)は実際には 3 ビットを消費しますが、完全に決定論的です。デルタ値は常に 3 ビットのみを消費します。

現在の予想ビット数での0は、各リンクに必要なビット数の増分を示すために使用されます。例えば、値マップ[ 1, 2, 2, 7, 15 ]（40 ビット）では、デルタ変換で[ 1, 0, 0, 7, 15 ]となり、必要なビット長は[ 3(delta), 3(delta), 3(delta), 3, 4 ]です。これを効率的にエンコードするために、ARJSON はデルタ以外の各増分の前に0を挿入します（デルタは常に 3 ビットが必要とわかっているため）。その結果 22 ビットとなり、18 ビットを節約します。

• 001(delta) 000(delta) 000(delta) 0(inc) 00(inc) 111(7) 000(inc) 1111(15)

これにより、ARJSON は追加のメタデータなしで次の値リンクを読み取るために必要な最小ビット数を常に決定できます。

デルタパッキング

同じデルタパターンが連続して 3 回以上発生する場合、ARJSON はデルタパッキングを適用して冗長な保存を排除します。例えば、値マップ[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]では、デルタ変換により[ 1, 1, 1, 1, 1, 1, 1, 1, 1 ]が得られ、27 ビット（値あたり 3 ビット）が必要です。繰り返しデルタを格納する代わりに、ARJSON はデルタパッキングを0（3 ビット）で示し、長さ9（4 ビット）と、デルタ値1（3 ビット）をエンコードして、わずか 10 ビット（000 1001 001）にします。これにより、単純なアプローチと比較して 17 ビットを節約します。

5. キーフラグ

キーフラグは、値フラグと同様に、キーがデルタエンコーディングを使用するかどうかを指定する 1 ビットの指標です。

6. キーリンク

キーリンクはキーマップ（[ -1, 0, 0, 0, 3 ]）を表しますが、最初の要素は常に-1なので削除されます。さらに、0はデルタパッキング用に予約されているため、[ -1, 0, 0, 0, 3 ]は[ 1, 1, 1, 4 ]に変換され、デルタ変換とパッキングによりさらに最適化されて[ 1, 0, 0, 3 ]になります。

7. キータイプ

キータイプはキーマップの各キーのタイプを定義する 2 ビットの指標です：

• 00（0）：配列
• 01（1）：オブジェクト
• 10（2）：base64url 文字列キー
• 11（3）：文字列キー

例えば、キーマップ["{}", "a", "b", "c", "[]"]の場合、キータイプは[1, 3, 3, 3, 0]になります。base64urlキーは 64 未満の数値に変換され、それぞれ 6 ビットだけでエンコードされるため、文字あたり少なくとも 2 ビットを節約します。通常の文字列キーは LEB128 を使用して格納されます。この最適化は、base64url 文字（英数字、-、_）のみで構成されるキーにのみ適用されます。

base64url または通常の文字列（タイプ2と3）として分類されるキーの場合、キータイプの後に圧縮フォーマットの文字列長が続きます。例えば、キーabcは10 00 11（10は base64url、00は 2 ビットの short エンコーディングを示し、11は長さ 3 を表す）として格納されます。

キータイプの後には、キータイプが文字列（10または11）の場合、キーの長さ（short）+ 1（0は重複参照用に予約されているため）が続きます。例えば、キーがabcの場合、キータイプは10 00 11です。

重複する文字列キーとタイプは、決定論的インデックスが続く0フラグに置き換えられ、ストレージのオーバーヘッドが大幅に削減されます。例えば、[ { "name": "Bob" }, { "name": "Alice" } ]では、nameの 2 回目の出現はbase64urlとして再度格納されず、代わりに10 000で参照され、最初の出現を指し示し、22 ビット（name対0、24 ビット対 2 ビット）を節約します。この方法は値の相互参照にも拡張されます。[ { "name": "Bob" }, { "Bob": "name" } ]では、nameとBobの両方が決定論的インデックス0と1にそれぞれ置き換えられ、さらに冗長性を削減します。

8. キー

キーはbase64url文字列または通常の文字列のいずれかです。前述のように、重複キーは決定論的インデックスに置き換えられ、冗長性が大幅に削減され、ビットを節約します。

9. データタイプ

ARJSON は 7 つのデータタイプを定義し、それぞれ 3 ビットだけで表現されます：

• 001（1）：null
• 010（2）：base64url文字列
• 011（3）：bool
• 100（4）：正の整数
• 101（5）：負の整数
• 110（6）：float
• 111（7）：文字列

値0はタイプパッキング用に予約されています。同じタイプが連続して 3 回以上出現する場合、リピートフラグ（0）、short 長エンコーディング、および実際のタイプを使用して圧縮されます。例えば、[ 3, 3, 3, 3, 3 ]は[ 0, 5, 3 ]に圧縮され、000 101 011として格納され、6 ビットを節約します。

10. ブール値

ブール値は 1 ビットで格納されます：

• 0：false
• 1：true

11. 数値

正の整数と負の整数はカスタム数値システムの 2 ビットフラグを使用して格納されます：

• 00（0）：デルタ
• 01（1）：4 ビット
• 10（2）：6 ビット
• 11（3）：LEB128

値がデルタエンコードされ（0フラグ）、次のビットが7の場合、デルタパッキングを示し、short 長と 3 ビットデルタ値が続きます。例えば、[ 1, 2, 3, 4, 5 ]（30 ビット）はまずデルタ変換で[ 1, 1, 1, 1, 1 ]に変換され、さらにデルタパッキングを使用して00 111 001に圧縮され、22 ビットを節約します。

浮動小数点数は、符号、精度、整数表現を使用して異なる方法で処理されます。最初の整数は符号と精度を組み合わせたもので、数値が負の場合は精度に 4 を加えます。精度が 2 より大きい場合、最初の整数は正の数の場合は0、負の数の場合は4を格納し、2 番目の整数は実際の精度を保持します。最後の整数は常に数値自体です。

例えば、-3.14は精度2の負の数で、最初の整数は6（2 + 4）、2 番目の整数は LEB128 フォーマットの314です。したがって、-3.14は01 0110 11 10011010 00000010となり、24 ビット（3 バイト）です。対照的に、MessagePack は-3.14を格納するために 9 バイトを消費します。

12. 文字列値

文字列値はキーと同じ圧縮ルールに従いますが、キー位置ではなく値位置に格納されます。例えば、{ "name": "Bob" }では、nameはキーとしてエンコードされ、Bobは文字列値として別々に格納されます。

13. パディング

エンコードされたビットストリームが適切なバイト整列を確保するために、最も近い 8 ビットの倍数にゼロパディングされます。エンコードされたデータが 29 ビットの場合、ARJSON はそれを 32 ビット（4 バイト）に拡張するために 3 つのパディングビットを追加し、効率的なバイトレベルのストレージを維持します。

プリミティブ値と空オブジェクトのための特別な最適化

最初のビットが1の場合、ARJSON は次の 7 ビットに構造化オブジェクトに使用されるものとは異なる特別なエンコーディングルールを適用します。これらの最適化により、プリミティブ値と空オブジェクトは最小限のオーバーヘッドで格納され、最大の圧縮効率が確保されます。

• 0：他の値タイプ
  • 00000（0）：null（00000000）
  • 00001（1）：true（00000001）
  • 00010（2）：false（00000010）
  • 00011（3）：""（00000011）
  • 00100（4）：[]（00000100）
  • 00101（5）：{}（00000101）
  • 00110（6）：負の整数、その後にuint（-1 => 00000110 001）
  • 00111（7）：正の浮動小数点数、その後にuint（精度）とuint（整数）
    （3.14 = > 00000111 00010111 01110100 00000010）
  • 01000（8）：負の浮動小数点数、その後にuint（精度）とuint（整数）
    （-3.14 = > 00001000 00010111 01110100 00000010）
  • 01001 - 111100（9-60）：アルファベットの単一文字（charmap + 9）
  • 111101（61）：アルファベット以外の単一文字：その後に LEB128（文字コード）
  • 111110（62）：アルファベットの複数文字：その後に short（charmap）
  • 111111（63）：アルファベット以外の複数文字：その後に LEB128（文字コード）
• 1：正の整数：その後に以下のいずれか
  • 63 以下の場合は 6 ビット整数（62 => 01111110）
  • 63 より大きい場合は111111と LEB128（70 => 63 + 7 => 01111111 00000111）

const charmap = { 
  A: 0, B: 1, C: 2, D: 3, E: 4, F: 5, G: 6, H: 7, I: 8,
  J: 9, K: 10, L: 11, M: 12, N: 13, O: 14, P: 15, Q: 16, R: 17,
  S: 18, T: 19, U: 20, V: 21, W: 22, X: 23, Y: 24, Z: 25,
  a: 26, b: 27, c: 28, d: 29, e: 30, f: 31, g: 32, h: 33, i: 34,
  j: 35, k: 36, l: 37, m: 38, n: 39, o: 40, p: 41, q: 42, r: 43,
  s: 44, t: 45, u: 46, v: 47, w: 48, x: 49, y: 50, z: 51
}

これらの特別なルールにより、64 未満の正の整数と単一のアルファベット文字、およびnull、true、false、""、[]、{}はすべてわずか 1 バイトでエンコードされ、効率性を最大化しながらストレージのオーバーヘッドを最小化します。

ベンチマーク

MessagePack、CBOR、BSON との比較ベンチマーク