那些从事数据压缩或想要编写自己的存档器的人可能会对本文感兴趣。
这篇文章主要是用Fabian Giesen维护的
博客资料撰写的。
引言
熵编码方法rANS（rangge + ANS）是FSE算法的同级算法，这是我之前
写的 。 缩写ANS表示
非对称数字系统 ，名称中的单词范围暗示了这种方法与
区间编码的相似之处。 rANS的作者是
Yarek Duda 。
通过rANS方法，您可以以极高的速度获得几乎最佳的压缩效果。 在这种情况下，rANS并不比FSE差，这并不奇怪：这两种算法都基于共同的理论基础。 但是，rANS算法比FSE更易于实现。
首先，将有很长的“理论”部分，然后我们将尝试编写一个简单的存档器。
方法说明
该算法的操作由以下简单公式确定：
编码： C(s,x): x := (x / Fs) * M + Bs + (x % Fs)解码： D(x): s = sym[x % M], x := Fs * (x / M) + (x % M) - Bs让我们详细分析它们。
编码函数
C（s，x）接收要编码的字符
s （使其为整数）和编码器
x的当前状态（也是整数）。
F s-符号频率
s 。 上面的Fs除数是整数。
M是字母表中所有符号频率的总和（
M = ΣF
s ）。
在s中 ，对应于编码字符的间隔的开始（在下图中）。
x ％
Fs是
x除以
F s的余数。
工作原理与
算术编码相同：我们将段
[ 0，
M）分成几部分，以使每个字符
s对应于一个间隔，该间隔的大小等于字符
s的频率。 在任何间隔中出现值
x％M表示相应符号的编码。
在编码开始时，
用任意合适的值初始化
x ，然后依次计算所有编码字符的函数
C（s，x） 。
函数
C（s，x）的每次计算都会增加
x的值。 当它太大时，应该将数据转储到输出中：
while (x >= x_max) { writeToStream(x % b);
此步骤称为
重新规范化 。 之后，您可以继续编码。
在代码上方，出现了新的常量：
x_max和
b 。 理论上，数字
M ，
b和
x_max是通过某种关系关联的，但是实际上，如果将状态uint32用于状态
x则使用以下值最有效：
M = 2 ^
k ，其中
k <= 16
b = 2 ^ 16（uint32的一半大小）
M = 2 ^
k的选择是由于在解码功能中存在被
M除的事实，因此可以用按位运算来替换其余部分的除法。
k的值是从以下考虑因素中选择的：
k值越大，
F s的精度越高，压缩效率越高。 在这种情况下，必须考虑到存储频率表的一些开销，因此使用
k的最大值并不总是值得的。
x_max的值应确保不发生溢出。 基于编码函数，我们得到
x <
uint32_max *
Fs /
M或略有不同的方式：
x_max <=（
b *
L ）*
Fs /
M ，其中
L <=
uint32_max /
b 。 在实际代码中，该条件采用x / b> = L / M * Fs的形式，以避免计算中的溢出。
选择
b = 2 ^ 16（uint32大小的一半）的方式是，如果
x超过
x_max ，则除以
b便足以继续工作。 结果，
while将在第一次迭代后结束，这意味着可以将其替换为简单的
if 。
结果，编码功能采用以下形式：
typedef uint32_t RansState; constexpr uint32_t RANS_L = 1u << 16; constexpr uint32_t k = 10;
在编码结束时，您必须保存
x的值，因为解码将从该值开始。 是的，我们将从头到尾解码，即从最后一个编码字符到第一个字符进行解码。 （在有关
FSE的文章中
，对这一点进行了足够详细的解释。）
我想再详细介绍一下编码公式的工作原理。
x := (x / Fs) * M + Bs + (x % Fs)
在计算（
x / Fs) * M ，变量
x包含
k个最低有效位（请回想
M = 2 ^
k ）。 加
+ Bs + (x % Fs)本质上是从字符
s的间隔开始向这些位写入某个值，因为
Bs是间隔的开始，并且（x％Fs）是此间隔内的数字（间隔的大小为Fs）。 因此，在解码时，我们可以通过其落入的间隔（x％M）确定编码的字符。
解码方式让我们继续进行解码功能。
D(x): s = sym[x % M], x := Fs * (x / M) + (x % M) - Bs
如上所述，所需字符
s由除法
x ％
M的余数确定
。 值（x％M）下降的间隔是这样的字符。
之前，我们专门定义了M = 2 ^ k以简化解码功能。 它最终像这样：
uint32_t RansDecode(RansState& x, RansInBuf& in) { assert(x >= RANS_L);
解码从在编码结束时获得的
x开始。 为此，必须将其与编码数据一起保存。
在解码结束时，解码器
x的状态应与编码完全相同。 通常，在每个步骤中
x必须与相应的编码步骤完全相同。 这个事实在调试时很有帮助。
如您所见，由于没有除法运算，因此解码比编码更快。
解码功能中最困难的时刻是确定值下降的间隔（x％M）的方法。
最简单，最快的方法是使用大小为
M的
sym []表
。 在这种情况下，我们得到的表大小与FSE算法中的表大小相同，不同之处在于，在rANS中，该表没有“混合”，字符是有序的，并且这样的表更易于构建。
这种方法的主要缺点是
符号表的大小，它随着
k的增加呈指数增长。
别名方法
发明了一种
别名方法来更有效地确定间隔中的命中。 使用此方法，您可以使用小表格快速确定所需的间隔-根据字母中的字符数。
在这里可以找到冗长而冗长的解释：
飞镖，骰子和硬币 。 我将简要描述该方法的本质：我们采用最长间隔的一部分并将其附加到最短间隔，以便总大小恰好为
M /
N （其中
N是字母中的字符数）。 事实证明，如果顺序执行此操作，则最终将得到
N对大小为
M /
N的对
。自然，
M必须可以被
N整除
。 如果我们回想起我们有
M = 2 ^
k ，那么字母表的大小原来也是2的幂。 这是没有问题的，因为您始终可以使用零频率的未使用字符将字母补充到所需的大小。
字符间隔被分成几部分的事实使编码过程复杂一点，但是却不多。 如果您还记得FSE，那么间隔通常会分布在整个范围内，好像是疯狂的混音器在处理它们，而没有任何效果=）
确定所需的间隔并不困难：将
x除以
N ，然后归为一对。 接下来，我们将
x％N除法的余数与成对线段之间的边界进行比较，并以一个间隔或另一个间隔落入。
我们在实践中尝试
我们将使用
完成示例的代码。
我们从文件中获取数据进行压缩：
size_t in_size; uint8_t* in_bytes = read_file("book1", &in_size);
1.首先，您需要确定
数据结构 。
我们使用最简单的选项：我们将使用字母[0 ... 255]编码一个字节。
2.下一步是确定字母
字符的
频率 ：
（功能
stats.count_freqs ）
for (size_t i = 0; i < in_size; i++) { freqs[in_bytes[i]]++; }
3.因此，我们有符号频率，但是现在我们需要对其进行
归一化 ，即成比例地减小（或增大），以便使总数为M = 2 ^ k。 这看起来并不简单，所以我们使用现成的函数：
stats.normalize_freqs(...);
顺便说一句，您需要确定
k的值。 由于我们的字母由256个字符组成，因此
k不应小于8。 首先，取最大值-16，然后再尝试其他值。
4.建立
别名表 ：
stats.make_alias_table();
5.我们 从头开始编码，然后以正常顺序解码。
RansState rans;
此外，通过引用的示例使用现成的统计信息对压缩数据进行解码。 在现实生活中，要进行解码，您需要保存一个频率表（统计信息）以及压缩数据。 在最简单的情况下，您将不得不在上面花费N * k位。
如上所述，让我们看看k的各种值的压缩结果（在代码中为
prob_bits ），同时考虑到由于记录频率表而导致的大小增加：
（
原书1文件 大小 ：768771）
k = 16：435059 + 512 = 435571字节
k =
15 ：435078 + 480 =
435558字节
k = 14：435113 + 448 = 435561字节
k = 13：435239 + 416 = 435655字节
k = 12：435603 + 384 = 435987字节
k = 11：436530 + 352 = 436882字节
k = 10：440895 + 320 = 441215字节
k = 9：453418 + 288 = 453706字节
k = 8：473126 + 256 = 473382字节
您会看到k越高，压缩效果越好。 但是在某个点（在k = 16处），频率表的开销开始超过增加精度的好处。 如果压缩较小的文件，则此效果将出现在较小的k上。
您还需要说几句有关“ interleaved rANS”的技巧，该技巧
在此示例中另外实现。 这个想法是交替使用两个独立的状态变量可以更好地利用处理器并行性。 结果，解码甚至更快。
总之，我想指出的是所选的文件压缩方法太简单了。 它没有考虑数据的特征，这就是压缩远非最佳的原因。 如果仔细看一下输入，您会发现某些
字母组合比其他
字母组合更常见，而有些根本没有。 利用这一事实，可以显着改善压缩。 但这是另一篇文章的主题。
后记
当有许多经过时间考验的实用程序时，为什么还要编写自己的存档器？ 答案很简单：针对特定格式量身定制的存档器压缩效果更好。
在
Playrix上开发游戏时，我们经常依靠减少构建大小的需求。 游戏不断发展，内容不断增长，而且空间有限。
再次
，我们
渴望地查看资源，我们意识到，鉴于文件的结构，某些文件的压缩比zip更好。 在实验过程中，我们设法显着减小了自己的动画格式的大小，并且图形文件的压缩也发生了一些变化。
在开发压缩算法时，诸如rANS或FSE之类的通用熵编码器是必不可少的工具。 它完全承担了编写位数最少的字符的任务，从而使开发人员可以专注于算法的主要细节。 而且它在编码和解码方面都非常快。
我希望本文能帮助您了解rANS并在您的项目中开始使用它。
参考文献
在这里，您可以看到rANS实施的工作示例（具有不同的优化选项）：
法比安·吉森（Fabian Giesen）：
github.com/rygorous/ryg_rans您可以在Fabian的博客上（英语）阅读有趣的详细信息：
→
rANS注释→
具有静态概率分布的rANS→
在实践中