メインコンテンツまでスキップ

11. 圧縮実装の考慮事項 (Considerations for Compressor Implementations)

11. 圧縮実装の考慮事項 (Considerations for Compressor Implementations)​

このドキュメントの目的は、特定の圧縮アルゴリズムを参照することなく brotli 圧縮データ形式を定義することであるため、このセクションの資料は形式の定義の一部ではなく、準拠するために圧縮プログラムがこれに従う必要はありません。

11.1. 簡易圧縮プログラム (Trivial Compressor)​

このセクションでは、次の C++ 言語関数の形式で、任意の非圧縮バイトシーケンスを表す有効な brotli ストリームを生成する非常にシンプルなアルゴリズムを提示します。

string BrotliCompressTrivial(const string& u) {
   if (u.empty()) {
      return string(1, 6);
   }
   int i;
   string c;
   c.append(1, 12);
   for (i = 0; i + 65535 < u.size(); i += 65536) {
      c.append(1, 248);
      c.append(1, 255);
      c.append(1, 15);
      c.append(&u[i], 65536);
   }
   if (i < u.size()) {
      int r = u.size() - i - 1;
      c.append(1, (r & 31) << 3);
      c.append(1, r >> 5);
      c.append(1, 8 + (r >> 13));
      c.append(&u[i], r + 1);
   }
   c.append(1, 3);
   return c;
}

このシンプルなアルゴリズムは実際にはデータを圧縮しないことに注意してください。つまり、brotli 表現は常に元のデータよりも大きくなりますが、N 個の非圧縮バイトのすべてのシーケンスは、N + (3 * (N >> 16) + 5) バイト以下の有効な brotli ストリームで表現できることを示しています。

11.2. 圧縮メタブロックのバイト境界への整列 (Aligning Compressed Meta-Blocks to Byte Boundaries)​

セクション 9 で説明されているように、非圧縮メタブロックまたはメタデータメタブロックの直後に続くメタブロックのみが、バイト境界で開始されることが保証されています。一部のアプリケーションでは、すべての非メタデータメタブロックがバイト境界で開始されることが要求される場合があります。これは、バイト境界で終了しないすべての非メタデータメタブロックの後に空のメタデータメタブロックを追加することで実現できます。

11.3. 圧縮データ内での自己完結部分の作成 (Creating Self-Contained Parts within the Compressed Data)​

一部のエンコーダー実装では、brotli ストリーム内のバイトシーケンスを自己完結型にする必要がある場合があります。つまり、圧縮データの以前の部分から独立して解凍できるようにする必要があります。これは 3 つの理由で有用な機能です。第 1 に、大きな圧縮ファイルが破損した場合、破損後のファイルの一部を回復することが可能です。第 2 に、圧縮データの差分転送を行う際に有用です。非圧縮バイトのシーケンスが変更されておらず、以前のデータから独立して圧縮されている場合、圧縮表現も変更されていない可能性があり、したがって非常に安価に転送できます。第 3 に、非圧縮バイトのシーケンスが独立して圧縮されている場合、複数のファイルの並列圧縮に加えて、同じファイル内でこれらのバイトシーケンスの並列圧縮が可能になります。

2 つの非圧縮バイトシーケンス U0 と U1 が与えられた場合、2 つの圧縮バイトシーケンス C0 と C1 を作成する方法について説明します。C0 と C1 の連結が有効な brotli ストリームであり、C0 と C1（ウィンドウサイズを含む C0 の最初のバイトとともに）が互いに独立して U0 と U1 に解凍できるようにします。

バイトシーケンス U0 を圧縮して C0 を生成する場合、次の 2 つの変更を加えて、非圧縮バイト U0 の完全なセット上で動作する任意の圧縮プログラムを使用できます。第 1 に、C0 の最後のメタブロックの ISLAST ビットを設定してはなりません。第 2 に、セクション 11.2 のように、空のメタデータメタブロックを追加することで、C0 がバイト境界で終了するようにする必要があります。

バイトシーケンス U1 を圧縮して C1 を生成する場合、次の 2 つの変更を加えて、U0+U1 入力ストリーム内の U1 の開始時に新しいメタブロックを開始する任意の圧縮プログラムを使用できます。第 1 に、C1 の後方距離は、静的辞書単語または U0 の非圧縮バイトを参照してはなりません。U1 のバイトシーケンスが静的辞書単語または U0 に重なるバイトシーケンスと一致する場合でも、圧縮プログラムは、代わりにリテラル挿入と U1 のバイトへの後方参照の組み合わせでこのバイトシーケンスを表現する必要があります。第 2 に、最後の 4 つの距離のリングバッファーは、C1 で他の距離をエンコードするために使用する前に、まず C1 の距離で補充する必要があります。C0 と C1 を生成する両方の圧縮プログラムは同じウィンドウサイズを使用する必要がありますが、ストリームヘッダーは C0 を生成する圧縮プログラムによってのみ出力されることに注意してください。

この方法は、2 つ以上の非圧縮バイトシーケンスに簡単に一般化できることに注意してください。

出典 (Source): RFC 7932, Section 11
公式テキスト (Official Text): https://www.rfc-editor.org/rfc/rfc7932.txt

に最終更新