4. 熵编码 (Entropy Encoding)

Zstandard格式使用两种类型的熵编码:FSE和Huffman编码.Huffman用于压缩字面量,而FSE用于所有其他符号（Literals_Length_Code、Match_Length_Code和偏移量码）以及压缩Huffman头部.

4.1. FSE

FSE是Finite State Entropy（有限状态熵）的缩写,是一种基于[ANS]的熵编解码器.FSE编码/解码涉及在符号之间携带的状态,因此解码必须以与编码相反的方向进行.因此,所有FSE位流都是从末尾到开头读取的.注意,流中位的顺序没有反转;它们只是按照与写入时相反的顺序读取.

有关FSE的更多详细信息,请参见"FiniteStateEntropy" [FSE].

FSE解码涉及具有2的幂大小并包含三个元素的解码表:Symbol（符号）、Num_Bits（位数）和Baseline（基线）.表大小的以2为底的对数是其Accuracy_Log（精度对数）.FSE状态值表示此表中的索引.

要获得初始状态值,从流中以小端值形式消耗Accuracy_Log位.流中的下一个符号是该状态的表中指示的Symbol.要获得下一个状态值,解码器应从流中以小端值形式消耗Num_Bits位并将其添加到Baseline.

要解码FSE流,需要构建解码表.Zstandard格式按照此处所述编码FSE表描述.

FSE分布表描述了从0到最后存在的符号（包括）的所有符号在(1 << Accuracy_Log)的归一化比例上的概率.注意,必须有两个或更多具有非零概率的符号.

位流以小端方式向前读取.它首先报告其操作的比例.如果low4bits表示第一个字节的最低4位,则Accuracy_Log = low4bits + 5.

然后是每个符号值,从0到最后存在的.每个字段使用的位数是可变的,取决于剩余概率和解码值.

Zstandard Huffman编码流与FSE位流类似,是向后读取的.因此,要找到位流的开始,需要知道Huffman编码流的最后一个字节的偏移量.

在写入包含信息的最后一位后,压缩器写入单个1位,然后用0位填充字节的其余部分.因此,压缩位流的最后一个字节不能为0.

解压时,包含填充的最后一个字节是要读取的第一个字节.解压器需要跳过最多7位的0填充以及第一个出现的1位.之后,位流的有用部分开始.

位流以小端顺序包含Huffman编码符号,代码由以下方法定义.

前缀编码通过位序列（码字）表示来自先验已知字母表的符号,每个符号一个码字,使得不同的符号可以由不同长度的位序列表示,但解析器总是可以明确地逐符号解析编码字符串.

给定具有已知符号频率的字母表,Huffman算法允许使用任何可能的前缀码中最少位数构建最优前缀码.

前缀码不得超过最大码长.更多位提高准确性但产生更大的头部大小并需要更多内存或更复杂的解码操作.本规范将最大码长限制为11位.