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

4. Entropy Encoding (エントロピー符号化)

Zstandard フォーマットは2種類のエントロピー符号化を使用します: FSE と Huffman 符号化です。Huffman はリテラル (Literals) の圧縮に使用され、FSE は他のすべてのシンボル (Literals_Length_Code、Match_Length_Code、およびオフセットコード) と Huffman ヘッダーの圧縮に使用されます。

4.1 FSE (有限状態エントロピー)​

FSE は Finite State Entropy (有限状態エントロピー) の略で、[ANS] に基づくエントロピーコーデックです。FSE エンコーディング/デコーディングはシンボル間で引き継がれる状態 (State) を伴うため、デコーディングはエンコーディングと逆の方向で行う必要があります。したがって、すべての FSE ビットストリーム (Bitstreams) は終端から先頭に向かって読み取られます。ストリーム内のビットの順序は逆転しないことに注意してください。ビットは単に書き込まれた順序とは逆の順序で読み取られます。

FSE の詳細については、"FiniteStateEntropy" [FSE] を参照してください。

FSE デコーディングには、2の累乗サイズを持ち、3つの要素を含むデコーディングテーブル (Decoding Table) が含まれます: Symbol (シンボル)、Num_Bits (ビット数)、Baseline (ベースライン)。テーブルサイズの2を底とする対数は Accuracy_Log (精度ログ) です。FSE 状態値はこのテーブル内のインデックスを表します。

初期状態値を取得するには、ストリームから Accuracy_Log ビットをリトルエンディアン値として消費します。ストリーム内の次のシンボルは、その状態のテーブルで示される Symbol です。次の状態値を取得するには、デコーダーはストリームから Num_Bits ビットをリトルエンディアン値として消費し、Baseline に追加する必要があります。

4.1.1 FSE Table Description (FSE テーブル記述)​

FSE ストリームをデコードするには、デコーディングテーブルを構築する必要があります。Zstandard フォーマットは、ここで説明されているように FSE テーブル記述をエンコードします。

FSE 分布テーブル (Distribution Table) は、0から最後に存在するシンボル (含む) までのすべてのシンボルの確率を正規化スケール (1 << Accuracy_Log) で記述します。非ゼロ確率を持つシンボルが2つ以上必要であることに注意してください。

ビットストリームはリトルエンディアン方式で順方向に読み取られます。正確なサイズを知る必要はありません。サイズはデコーディングプロセスによって発見され、報告されます。ビットストリームは最初に動作するスケールを報告します。low4bits が最初のバイトの最下位4ビットを指定する場合、Accuracy_Log = low4bits + 5 です。

これに続いて、0から最後に存在するシンボルまでの各シンボル値が続きます。各フィールドで使用されるビット数は可変であり、次に依存します:

残りの確率 + 1 : たとえば、Accuracy_Log が8で、すでに100の確率ポイントが配分されていると仮定すると、デコーダーは0から (256 - 100 + 1) == 157 (含む) までの任意の値を読み取ることができます。したがって、log₂(157) == 8 ビットを読み取る必要があります。

デコードされた値 : 小さい値は1ビット少なく使用します。たとえば、0から157 (含む) までの値が可能であると仮定すると、255 - 157 = 98 個の値が8ビットフィールドに残ります。最初の98個の値 (したがって0から97まで) は7ビットのみを使用し、98から157までの値は8ビットを使用します。これは表20のスキームによって実現されます:

+============+===============+===========+
| Value Read | Value Decoded | Bits Used |
+============+===============+===========+
|   0 - 97   |     0 - 97    |     7     |
+------------+---------------+-----------+
|  98 - 127  |    98 - 127   |     8     |
+------------+---------------+-----------+
| 128 - 225  |     0 - 97    |     7     |
+------------+---------------+-----------+
| 226 - 255  |   128 - 157   |     8     |
+------------+---------------+-----------+

表20: デコードされた値

シンボル確率は順番に1つずつ読み取られます。確率は式 P = Value - 1 を使用してデコードされた値 (Value Decoded) から取得されます。これは、値0が負の確率-1になることを意味します。これは「1未満」を意味する特別な確率です。分布テーブルへの影響については後述します。合計配分確率ポイントを計算する目的では、1としてカウントされます。

シンボルの確率がゼロの場合、2ビットの繰り返しフラグ (Repeat Flag) が続きます。この繰り返しフラグは、現在のシンボルに続くゼロ確率の数を示します。0から3までの数値を提供します。3の場合、別の2ビットの繰り返しフラグが続き、以下同様です。

最後のシンボルが累積合計 (1 << Accuracy_Log) に達すると、デコーディングが完了します。最後のシンボルが累積合計を (1 << Accuracy_Log) を超えさせる場合、分布は破損していると見なされます。

最後に、デコーダーはこのプロセスで使用されたバイト数と存在するシンボルの数を知ることができます。ビットストリームは整数バイトを消費します。最後のバイト内の残りのビットは単に未使用です。

テーブルが使用されるコンテキストは、予想されるシンボル数を指定します。その予想シンボル数は256を超えません。デコードされたシンボルの数が予想と等しくない場合、ヘッダーは破損していると見なされるべきです。

正規化された確率の分布は、一意のデコーディングテーブルを作成するのに十分です。テーブルのサイズは (1 << Accuracy_Log) です。各セルは、デコードされたシンボルと次の状態を取得するための指示を記述します。

シンボルは、上記の「1未満」の確率について自然な順序でスキャンされます。この確率を持つシンボルには、テーブルの終端から始めて後退しながら単一のセルが割り当てられます。これらのシンボルは完全な状態リセット (Full State Reset) を定義し、Accuracy_Log ビットを読み取ります。

残りのすべてのシンボルは自然な順序で割り当てられます。シンボル0とテーブル位置0から始めて、各シンボルはその確率と同じ数のセルを割り当てられます。セルの割り当ては分散されており、線形ではありません。各後続位置は次のルールに従います:

position += (tableSize >> 1) + (tableSize >> 3) + 3;
position &= tableSize - 1;

位置がすでに「1未満」の確率シンボルによって占有されている場合、その位置はスキップされます。位置はシンボル間でリセットされません。現在のシンボルに十分な状態が割り当てられたときに次のシンボルに切り替えながら、テーブル内の各位置を単に反復します。

結果は状態値のリストです。各状態は現在のシンボルをデコードします。

次の状態に必要な Number_of_Bits と Baseline を取得するには、まずすべての状態を自然な順序でソートする必要があります。下位の状態は上位の状態よりも1ビット多く必要になります。このプロセスは各シンボルに対して繰り返されます。

例: シンボルの確率が5であると仮定すると、5つの状態値を受け取ります。状態は自然な順序でソートされます。次の2の累乗は8です。確率空間は8つの等しい部分に分割されます。Accuracy_Log が7であると仮定すると、これは128の状態を定義し、各シェア (8で除算) のサイズは16です。8に到達するために、8 - 5 = 3 の最下位状態は「ダブル」カウントされ、シェア数を2倍 (幅32) にし、プロセスでさらに1ビットを必要とします。

Baseline は、より少ないビットを使用するより高い状態から開始して割り当てられ、自然に進み、その後最初の状態から再開し、各状態は Baseline から割り当てられた幅を取得します。

+----------------+-------+-------+--------+------+-------+
|  state order   |   0   |   1   |   2    |  3   |   4   |
+----------------+-------+-------+--------+------+-------+
|     width      |   32  |   32  |   32   |  16  |   16  |
+----------------+-------+-------+--------+------+-------+
| Number_of_Bits |   5   |   5   |   5    |  4   |   4   |
+----------------+-------+-------+--------+------+-------+
|  range number  |   2   |   4   |   6    |  0   |   1   |
+----------------+-------+-------+--------+------+-------+
|    Baseline    |   32  |   64  |   96   |  0   |   16  |
+----------------+-------+-------+--------+------+-------+
|     range      | 32-63 | 64-95 | 96-127 | 0-15 | 16-31 |
+----------------+-------+-------+--------+------+-------+

表21: Baseline割り当て

次の状態は、必要な Number_of_Bits を読み取り、指定された Baseline を追加することによって現在の状態から決定されます。

デフォルト分布に適用されるこのプロセスの結果については、付録Aを参照してください。

4.2 Huffman Coding (ハフマン符号化)​

Zstandard Huffman 符号化ストリームは、FSE ビットストリームと同様に逆方向に読み取られます。したがって、ビットストリームの開始を見つけるには、Huffman 符号化ストリームの最後のバイトのオフセットを知る必要があります。

情報を含む最後のビットを書き込んだ後、コンプレッサーは単一の1ビットを書き込み、その後バイトの残りを0ビットで埋めます。そのため、圧縮ビットストリームの最後のバイトは0にはなりません。

解凍時、パディングを含む最後のバイトが最初に読み取るバイトです。デコンプレッサーは、最大7ビットの0パディングと、発生する最初の1ビットをスキップする必要があります。その後、ビットストリームの有用な部分が始まります。

ビットストリームには、リトルエンディアン順序で Huffman 符号化されたシンボルが含まれており、コードは以下の方法で定義されます。

4.2.1 Huffman Tree Description (ハフマン木記述)​

プレフィックス符号化 (Prefix Coding) は、事前に既知のアルファベットからのシンボルをビットシーケンス (コードワード) で表現し、各シンボルに1つのコードワードを割り当てます。異なるシンボルは異なる長さのビットシーケンスで表現される場合がありますが、パーサーは常に符号化された文字列を明確にシンボルごとに解析できます。

既知のシンボル頻度を持つアルファベットが与えられると、Huffman アルゴリズムは、そのアルファベットのすべての可能なプレフィックスコードの中で最小ビット数を使用して最適なプレフィックスコードを構築できます。

プレフィックスコードは最大コード長を超えてはなりません。より多くのビットは精度を向上させますが、より大きなヘッダーサイズを生成し、より多くのメモリまたはより複雑なデコーディング操作を必要とします。この仕様では、最大コード長を11ビットに制限しています。

ゼロ (含む) から最後に存在するリテラル値 (除く) までのすべてのリテラル値は、0から Max_Number_of_Bits までの値を持つ Weight (重み) で表されます。Weight から Number_of_Bits への変換は、この擬似コードに従います:

if Weight == 0:
    Number_of_Bits = 0
else:
    Number_of_Bits = Max_Number_of_Bits + 1 - Weight

最後のシンボルの Weight は、以前にデコードされたものから推定され、最も近い2の累乗に完成させます。この2の累乗は Max_Number_of_Bits、つまり現在の木の深さを与えます。

(以降、表22-26とHuffman符号化ストリームの詳細が続きます)

に最終更新