Huffman符号化

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

圧縮器は、情報を含む最後のビットを書いた後に1ビットを1つ書き、続けて0～7個の0ビットのパディングでバイトを埋めます。 このため、圧縮ビットストリームの最後のバイトは0にはなりません。

伸長時には、パディングを含む最後のバイトを最初に読みます。 伸長器は、先頭の0～7個の0ビットと、最初に現れる1ビットを飛ばす必要があります。 その後に、ビットストリームの有効部分が始まります。

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

Huffman木の記述

接頭符号化は、あらかじめ既知のアルファベットのシンボルを、シンボルごとに1つのビット列（符号語）で表します。 異なるシンボルを長さの異なるビット列で表せますが、パーサーは常に、符号化された文字列をシンボルごとに曖昧さなく解析できます。

シンボルの頻度が既知のアルファベットに対し、Huffmanアルゴリズムは、そのアルファベットのあらゆる接頭符号の中で最少のビットを使う、最適な接頭符号を構築できます。

接頭符号は、符号長の上限を超えてはなりません。 ビット数を増やすと精度は上がりますが、ヘッダーサイズが増え、より多くのメモリや、より複雑な復号操作が必要になります。 この仕様では、最大符号長を11ビットに制限します。

表現

ゼロ（含む）から最後に存在するリテラルシンボル（含まない）までの全シンボルは、0からMax_Number_of_BitsまでのWeightで表します。 WeightからNumber_of_Bitsへの変換は、次の式に従います:

Number_of_Bits = Weight ? (Max_Number_of_Bits + 1 - Weight) : 0

存在しないリテラルシンボルには、Weightとして0を与えます。 最も頻度の低いシンボルには、Weightとして1を与えます。 Weightが1のリテラルが存在しなければ、データは破損していると見なします。 ゼロでないWeightを持つリテラルが2つ以上存在しなければ、データは破損していると見なします。 最も頻度の高いシンボルには、1から11（最大）までのいずれかのWeightを与えます。 最後のシンボルのWeightは、取得済みの重みから、最も近い2の累乗に達するように補って導きます。この値は必ずゼロ以外です。 1つのWeight値でちょうど2の累乗に達せない場合、Huffman木の記述は無効と見なします。 最終的な2の累乗から、現在の木の深さであるMax_Number_of_Bitsを得ます。 Max_Number_of_Bitsは11以下でなければならず、それを超える表現は破損していると見なします。

例: 次のHuffman木を記述するものとします:

最も長い要素は4ビットを使うので、木の深さは4です（最も長い要素は、最も頻度の低いものです）。

すべてのシンボルに、Number_of_Bitsの代わりにWeightを与えます。重みの式は次のとおりです:

Weight = Number_of_Bits ? (Max_Number_of_Bits + 1 - Number_of_Bits) : 0

これにより、次の重みの列を得ます:

このリストは、次の変更を加えてデコーダーへ送ります:

• Fは、先行シンボルから決定できるため、列挙しません。
• Fより後のシンボルも、すべて0であるため、列挙しません。
• 一方、Aより前のシンボルは、\0から始めてすべて、重み0で列挙します。

デコーダーは逆の操作を行います。 AからEまでのリテラルシンボルの重みを集めると、最後のリテラルFがゼロでないWeightを持って存在すると分かります。 FのWeightは、次の2の累乗まで進めることで決定できます。 2^(Weight-1)の合計（ゼロを除く）は、8 + 4 + 2 + 0 + 1 = 15です。 これより大きい、最も近い2の累乗は16です。 したがって、Max_Number_of_Bits = log2(16) = 4、Weight[F] = log_2(16 - 15) + 1 = 1です。

Huffman木のヘッダー

これは、重みの列の符号化方法を記述する1バイトの値（0～255）です。

• headerByte < 128の場合: 重みの列は、FSEで圧縮します（後述）。 FSEで圧縮した列の長さはheaderByte（0～127）です。

• headerByte >= 128の場合:

  • 重みの列は直接表現を使い、各Weightを4ビットフィールド（0～15）として直接符号化します。
  • 順方向に、1バイトあたり2つの重みを符号化します。最初の重みが上位4ビット、次の重みが下位4ビットを取ります。
    • たとえば、重みの読み取りにWeight[0] = (Byte[0] >> 4), Weight[1] = (Byte[0] & 0xf)などの操作を使えます。
  • 表現全体はCeiling(Number_of_Weights/2)バイトを占めます。 Number_of_Weightsが奇数でも、常に整数個のバイトを使います。
  • Number_of_Weights = headerByte - 127です。
    • Number_of_Weightsの最大値は255-127 = 128なので、直接表現で符号化できるWeightは最大128個です。
    • 最後のゼロでないWeightは符号化しないため、この方式は最大129シンボルのアルファベットに対応し、リテラルシンボル128も含められます。
    • 128を超えるリテラルシンボルのいずれかが、ゼロでないWeightを持つ場合、直接表現はできません。この場合には、FSE圧縮が必要です。

Huffmanの重みに対するFinite State Entropy（FSE）圧縮

この場合、Huffmanの重みの列をFSE圧縮で圧縮します。 これは、1つの分布表を共有する2つの状態を交互に使う、単一のビットストリームです。

FSEビットストリームの復号には、その圧縮サイズを知る必要があります。 圧縮サイズはheaderByteで与えます。 また、伸長後サイズの可能な最大値も知る必要があり、これは255です。 リテラルシンボルは0から255まであり、最後のシンボルのWeightは表現しないためです。

FSEビットストリームの先頭には、確率分布を記述するヘッダーがあります。これによって復号表を作成します。 Huffmanの重みのリストに対するaccuracy logの最大値は6ビットです。 詳細はFSEヘッダーの記述を参照してください。

Huffmanヘッダーの圧縮には、同じFSE分布表を共有する2つの状態を使います。 最初の状態（State1）は偶数インデックスのシンボルを符号化し、2つ目の状態（State2）は奇数インデックスのシンボルを符号化します。 まずState1、続いてState2を初期化し、その後は交互に、1シンボルの復号と状態の更新を行います。 これらのFSE操作の詳細はFSEの節を参照してください。

復号するシンボル数は、ビットストリームのオーバーフロー条件を追跡して決めます。 シンボルの復号後に状態を更新する際、ストリームの残りのビット数より多くのビットが必要になる場合、余分なビットは0と見なします。 その後、最後の各状態のシンボルを復号して処理を完了します。

この処理で、復号する重みの最大数（255）を超える重みが生成される場合、データは破損していると見なします。

2つの初期状態のいずれかが欠けているか途中で切れている場合、データは破損していると見なします。 したがって、このモードで2個未満の重みを符号化することはできません。

重みからHuffman接頭符号への変換

存在するすべてのシンボルに、Weight値がある状態になりました。 次の式を使い、重みからNumber_of_Bitsへ変換できます:

Number_of_Bits = (Weight>0) ? Max_Number_of_Bits + 1 - Weight : 0

各シンボルにどの接頭符号を割り当てるかを決めるために、まずWeight順、次に自然な連続順序でシンボルを並べます。 Weightがゼロのシンボルは除きます。 次に、最小のWeight（つまり最大のNumber_of_Bits）から始めて、昇順に接頭符号を割り当てます。

例: 次の重みのリストを復号したものとします:

重み順、次に自然な連続順序で並べると、接頭符号は次のように分布します:

Huffman符号化ストリーム

Huffman復号表があれば、Huffman符号化ストリームを復号できます。

各ビットストリームは逆方向、つまり末尾から先頭へ読む必要があります。 そのため、各ビットストリームのサイズを知る必要があります。

また、どのビットが最後かを正確に知る必要があります。 これは終端ビットフラグで検出します。最後のバイトの最も上位の立っているビットが終端ビットフラグです。 したがって、最後のバイトが0になることはありません。 終端ビットフラグ自体は、有効なビットストリームの一部ではありません。 このため、最後のバイトに含まれる有効ビットは0～7個です。

末尾から始め、使用済みのビットを追跡しながら、リトルエンディアンでビットストリームを読むことができます。 ビットストリームは逆順に符号化されているため、末尾から読み始めると、シンボルを順方向に読み取れます。

たとえば、上の接頭符号を使ってリテラル列ABEFを符号化すると、次のように（逆順で）符号化します:

結果として、次の2バイトのビットストリームになります:

00010000 00001101

各シンボルの符号をアンダースコアで区切った別表現は次のとおりです:

0001_0000 00001_1_01

上位のMax_Number_of_Bitsビットを読み取り、取り出した値を復号表と照合すると、復号するシンボルと捨てるビット数を決められます。

この処理を、各ストリームで必要な数のシンボルを読み取るまで続けます。 ビットストリームを過不足なくすべて消費できなかった場合、つまりすべてのビットを消費してちょうど先頭の位置に到達できなかった場合、復号処理は誤りと見なします。