ANS(非对称数字系统) + FSE(有限状态熵)

一、公式介绍

FSE(Finite State Entropy)是ANS(Asymmetric Numeral System)的一个具体实现，被应用在zstd压缩算法中，综合素质非常优异。本质是通过原字符串的信息加上新增字符后，通过新增字符的信息获取新的字符串的整体信息。即：

其中：

• 表示字符串中的单个字符；
• 表示字符串的一个状态信息；
• 表示一个处理函数，通过原字符串的状态信息及新增的字符获取新字符串的状态信息；

状态信息

这里的状态信息指的是可以唯一表示一个字符串的一个数字。
对于一个二进制字符串，编码时，他的状态信息可以直接用其对应的十进制数字来表示。

处理函数

对于一个状态信息，我们可以得到的信息熵（这里可以理解为通过二进制表示时的长度）为：

对于一个新字符串状态的信息熵，我们可以使用旧字符串状态的信息熵通过以下方式得到：

即：

其中：

• 表示字符串的一个状态信息；
• 表示字符串的信息熵；
• 表示字符串中的单个字符的信息熵；
• 表示单个字符在字符串中出现的概率；

由于以上的公式是根据新增的字符对应的概率算的，实际应用是还需要考虑不同字符概率相同的场景，此时我们可以得到一个简单的处理函数：

其中表示与字符相关的一个值。

二、应用

1. 编码

存在一个长度为待压缩的字符串，其中共包含的种字符，每个字符在字符串中出现的次数为，为了方便计算，通常对次数进行标准化，将总次数限制为，即。

压缩前需要构建一个累计分布统计参数，用该值来唯一区分各个字符，即有：

其中：

假设字符流的状态值为，同时指定初始状态值，为一个任意正整数。
则根据编码公式有：

其中：。

为方便计算，整个过程中需要保持为整数运算，因此对向下进行取整，同时在最后加上和的余数进行修正，防止结果计算错误。
修正后的编码公式为：

最终对于字符串，计算完成后我们会得到一个状态值，此时就压缩完成了，压缩后的数据仅需要包含：

• 字符集；
• 每个字符在字符串中出现的次数为；
• 字符串的长度；
• 状态值。

2. 解码

解码过程就是对编码的公式进行反推，根据上一次的状态值，获取当前位置的字符及当前状态值，将字符串从后往前一个个进行解压，与压缩的顺序刚好相反。
获取字符前需要先构建累计分布统计参数

其中。

然后再根据上次状态值的余数判断一下范围：

其中。

就可以确定当前位置的字符为：

获取当前状态值：

3. 量化状态值

实际压缩过程中，字符串的长度总是非常长的，状态值很容易就会超过整数取值范围，这时候我们可以通过位移来让总是保持在这个范围内，当超出这个范围时，将的低位保存起来，然后将右移位。
同理，在解压的时候，当小于这个范围时，将其左移位再进行处理。

三、拓展

1. tANS

tANS通过提前构建一个编码表来加速在编码过程中的运算过程。
编码表包含行数据，每个字符有自己的一行数据，行内存的是所有可能的状态值。
假设下面是一个编码表A：

	1	2	3	…
		…	…	…
…	…	…	…	…
	…	…	…	…

压缩：

压缩字符过程中，计算出后，将填到表格的位置。

解压

通过上一个的状态值，直接在表A中查找到该值对应的位置，所在行下标可以对应找出当前字符，所在列下标即为当前的状态值。