エントロピー符号化

Zstandard形式では、FSEとHuffman符号化という2種類のエントロピー符号化を使います。 Huffmanはリテラルの圧縮に使い、FSEはその他すべてのシンボル （Literals_Length_Code、Match_Length_Code、オフセットコード）と、Huffmanヘッダーの圧縮に使います。

FSE

FSEはFinite State Entropyの略で、ANSに基づくエントロピーコーデックです。 FSEの符号化・復号では、シンボル間で引き継ぐ状態を使います。 復号は符号化と逆の方向に行う必要があります。そのため、すべてのFSEビットストリームは末尾から先頭へ読みます。 ストリーム内のビット順を逆転させるのではなく、複数ビットからなる各要素を、符号化した順序と逆順に読むだけである点に注意してください。

FSEの詳細はFinite State Entropyを参照してください。

FSEの復号は、サイズが2の累乗である復号表に従います。各行はSymbol、Num_Bits、Baselineの3要素を含みます。 表のサイズのlog2がAccuracy_Logです。FSE状態値は、この表のインデックスを表します。

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

FSE表の記述

FSEビットストリームを復号するには、FSE復号表を構築する必要があります。 復号表は確率分布から導きます。Zstandard形式は、確率分布を次のように符号化します。

確率分布は、リトルエンディアンで順方向に読むビットストリームによって記述します。 分布の記述に消費したバイト数は、復号処理の終了時に判明します。

ビットストリームの先頭では、分布の尺度を通知します。 最初のバイトの下位4ビットをlow4Bitsとすると、Accuracy_Log = low4bits + 5です。

FSE分布表は、0から最後に存在するシンボルまで（両端を含む）、すべてのシンボルの確率を自然順で記述します。 確率の合計は、2の累乗である1 << Accuracy_Logになるように正規化します。 確率がゼロでないシンボルが、2つ以上存在しなければなりません。

各確率の復号に使うビット数は可変で、次の要素によって決まります:

• 残りの確率の合計 + 1: 例: Accuracy_Logが8で、100個の確率ポイントがすでに割り当てられているとします。 デコーダーは、0から256 - 100 + 1 == 157まで（両端を含む）の任意の値を読み取れます。 したがって、最大でlog2sup(157) == 8ビットを読み取れます。 ここでlog2sup(N)は、(1 << T) > Nを満たす最小の整数Tです。

• 復号する値: 小さい値は1ビット少なくなります。 例: 0から157まで（両端を含む）の値を取れる場合、8ビットのフィールドには255-157 = 98個の値が余ります。 これを次のように利用します。最初の98個の値（0から97）は7ビットだけを使い、98から157は8ビットを使います。 次の方式で実現します:

  読み取った8ビットフィールド	復号値	消費ビット数
  0 - 97	0 - 97	7
  98 - 127	98 - 127	8
  128 - 225	0 - 97	7
  226 - 255	128 - 157	8

確率は、復号した値から次の式で導きます: Probality = Value - 1

したがって、確率0は値1で記述します。

値0は、「確率-1」と呼ぶ特殊なケースを示すために使います。 これは「1未満」であるはずの確率を表します。 復号表の構築への影響は次の節で説明します。 割り当て済み確率ポイントの合計を数える際には、1として数えます。

シンボルの確率は、順番に1つずつ読み取ります。 各確率を復号するたびに、確率ポイントの合計を更新します。 この合計を使って、次のシンボルの確率を復号するために読むビット数を決めます。

シンボルの確率がzero（値1を読み取って復号したもの）の場合、後ろに2ビットの繰り返しフラグが続きます。 このフラグは、現在の確率の後に続く確率ゼロの個数を示し、0から3の値を取ります。 値が3の場合は、さらに別の2ビットの繰り返しフラグが続き、このように繰り返します。

あるシンボルの確率によって累計が1 << Accuracy_Logに達したら、そのシンボルが最後であり、復号は完了です。

この時点で、デコーダーは処理に使ったバイト数と、存在するシンボル数を判断できます。 ビットストリームは整数個のバイトを消費します。最後のバイトに残るビットは使いません。

この処理により、FSE表が定義されている有効なシンボル範囲の外にあるシンボルにゼロでない確率が与えられた場合、 そのシンボルを使っていなくても、データは破損していると見なします。 オフセットコードの場合には、デコーダー実装が対応する最大のオフセットコードを超えるコードにゼロでない確率があるフレームを、その実装が拒否してもかまいません。

正規化分布から復号表へ

正規化された確率分布だけで、一意の復号表を作成できます。次の構築規則を使って生成します:

表のサイズはTable_Size = 1 << Accuracy_Logです。 各行は、復号シンボルと、次の状態へ進むための指示（Number_of_BitsとBaseline）を指定します。

まず、自然順にシンボルを走査して「1未満」の確率（値0から復号したもの）を探します。 この特殊な確率を持つシンボルには、表の末尾から逆方向に1行ずつ割り当てます。 これらのシンボルは、Accuracy_Logビットを読む、状態の完全なリセットを定義します。

次に、残るシンボルをすべて自然順に並べ、行を割り当てます。 存在する最小のシンボルと表の位置0から開始し、各シンボルにその確率と同数の行を割り当てます。

行の割り当ては線形ではなく、剰余演算による次の順序に従います:

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

上の順序規則に従い、各シンボルにその確率と同数の行を割り当てます。 ある位置が「1未満」の確率のシンボルに占有されている場合は、その位置を飛ばし、代わりに次の位置を割り当てます。 現在のシンボルに十分な行を割り当てたら、自然順で次のシンボルに処理を続けます。 この処理により、表全体が過不足なく埋まることが保証されます。

各行は、復号シンボルを指定し、現在の状態値で参照します。 また、次の状態値を決めるために必要なNumber_of_BitsとBaselineも指定します。

これらのフィールドを正しく設定するには、各シンボルが出現するすべての行を状態値の順に並べ、 下側の行にN+1ビット、上側の行にNビットを割り当てる必要があります。以下の手順で説明します（例を使用します）:

例: Accuracy_Logが7で、あるシンボルの確率が5であるとします。 このシンボルは、0から127までの5つの状態値に対応する5行を受け取ります。

この例では、最初の状態値は（ここで指定していない先行シンボルの後の）1とします。 残り4つの状態は、上の剰余演算の規則で決めます。 次の位置へ移るために64+16+3 = 83を加え、128を法とするため、1、84、39、122、77という並びになります。 （次のシンボルは32から開始します。）

これらの状態値を自然順に並べると、1、39、77、84、122となります。

5の次の2の累乗は8です。そのため、確率空間を8等分します。 確率空間の大きさは1<<7 = 128なので、各部分の大きさは128/8 = 16です。

8つの部分に達するように、下位の8-5 = 3個の状態を「2倍」と数えます。 割り当てを2倍（幅32）にするため、1ビット多く必要になります。

Baselineは、より少ないビットを使う最小の状態から割り当て始め、状態値の自然順に進み、最後は先頭に戻ります。 各状態は、Baselineから始まり、そのNumber_of_Bitsに応じた大きさの割り当て範囲を取ります。

復号時には、現在の状態値を行番号に使い、必要なNumber_of_Bitsをビットストリームから読み取って、指定されたBaselineを加算することで、次の状態値を決めます。

注: 単純な例として、確率が1のシンボルでは、Baselineは必ず0、Number_of_Bitsは必ずAccuracy_Logになります。

この処理を既定の分布に適用した結果は付録Aを参照してください。