tANS 状态集的最小大小以安全地编码符号帧
tANS Mininum Size of State Set to Safely Encode a Symbol Frame
您好，我正在尝试在计算着色器中实现 tANS，但我对状态集的大小感到困惑。也很抱歉，但我的帐户太新，无法嵌入乳胶格式方程式的图片。
假设我们有一个符号框架 S，由符号 s₁ 到 sₙ 组成：
S = {s₁, s₂, s₁, s₂, ..., sₙ}
|S| = 2ᵏ
每个符号出现的概率为
pₛₙ = 频率(sₙ) / |S|
∑ pₛ₁ + pₛ₂ + ... pₛₙ = 1
根据 Jarek Duda 的幻灯片 (which can be found here)，构建编码函数的第一步是计算状态数 L:
L = |S|
这样我们就可以创建一组状态
= {L, ..., 2L - 1}
我们可以从中构建编码table。在我们的示例中，这很简单 L = |S| = 2^k。但是，我们不希望 L 一定等于 |S|因为|S|可能是巨大的，并构建一个对应于大小 |S| 的编码 table压缩会适得其反。 Jarek 的解决方案是创建一个量化函数，这样我们就可以选择一个
L : L < |S|
近似符号概率
Lₛ / L ≈ pₛₙ
然而随着L的减小，压缩质量下降，所以我有两个问题：
- 在实现压缩的同时，我们可以将 L 缩小到多小？
- 确定给定 |S| 的 L 大小的“好”方法是什么？
在 Jarek 的 ANS toolkit 中，他使用从 S 创建的霍夫曼树的深度来获得 L 的大小，但是当我们已经知道 L 的上限时，这似乎需要大量工作（|S |；据我所知，当 L = |S| 时，我们处于香农熵；因此使 L > |S| 不会增加压缩）。相反，选择同时小于 |S| 的 L 似乎会更快并且高于某个最小 L。因此，L 的“良好”大小将实现一定程度的压缩，但更重要的是，它很容易计算。然而，我们需要确定最小 L。根据示例 ANS tables 的图片，L 的最小大小似乎是最可能符号的频率，但我对 ANS 了解不够确认这一点。
想了想，两个问题的答案都很简单。仍然实现无损压缩的最小 L 是 L = |A|，其中 A 是要编码的符号字母表（抱歉，无损标准应该包含在原始问题中）。如果 L < |A|那么我们就是在归类符号，从而丢失信息。当 L = |A|我们本质上拥有的是一个固定长度的可变代码，其中每个符号在我们的编码中具有相等的概率权重 table。既然我们知道了第一个问题的答案，那么第二部分的答案就更加简单了。 L 几乎可以是任何你想要的，只要它大于要编码的字母表的大小。通常我们希望 L 是 2 的幂以提高计算效率，然后我们希望 L 大于 |A|为了实现更好的压缩，所以一个非常常见的 L 大小是等于或大于字母表大小的 2 的最大幂的 2 倍。这可以很容易地通过这样的东西找到：
int alphabetSize = SizeOfAlphabet();
int L = pow(2, ceil(log(alphabetSize, 2)) + 1);
您好，我正在尝试在计算着色器中实现 tANS，但我对状态集的大小感到困惑。也很抱歉，但我的帐户太新，无法嵌入乳胶格式方程式的图片。
假设我们有一个符号框架 S，由符号 s₁ 到 sₙ 组成：
S = {s₁, s₂, s₁, s₂, ..., sₙ}
|S| = 2ᵏ
每个符号出现的概率为
pₛₙ = 频率(sₙ) / |S|
∑ pₛ₁ + pₛ₂ + ... pₛₙ = 1
根据 Jarek Duda 的幻灯片 (which can be found here)，构建编码函数的第一步是计算状态数 L:
L = |S|
这样我们就可以创建一组状态
= {L, ..., 2L - 1}
我们可以从中构建编码table。在我们的示例中，这很简单 L = |S| = 2^k。但是，我们不希望 L 一定等于 |S|因为|S|可能是巨大的，并构建一个对应于大小 |S| 的编码 table压缩会适得其反。 Jarek 的解决方案是创建一个量化函数，这样我们就可以选择一个
L : L < |S|
近似符号概率
Lₛ / L ≈ pₛₙ
然而随着L的减小，压缩质量下降，所以我有两个问题：
- 在实现压缩的同时，我们可以将 L 缩小到多小？
- 确定给定 |S| 的 L 大小的“好”方法是什么？
在 Jarek 的 ANS toolkit 中，他使用从 S 创建的霍夫曼树的深度来获得 L 的大小，但是当我们已经知道 L 的上限时，这似乎需要大量工作（|S |；据我所知，当 L = |S| 时，我们处于香农熵；因此使 L > |S| 不会增加压缩）。相反，选择同时小于 |S| 的 L 似乎会更快并且高于某个最小 L。因此，L 的“良好”大小将实现一定程度的压缩，但更重要的是，它很容易计算。然而，我们需要确定最小 L。根据示例 ANS tables 的图片，L 的最小大小似乎是最可能符号的频率，但我对 ANS 了解不够确认这一点。
想了想，两个问题的答案都很简单。仍然实现无损压缩的最小 L 是 L = |A|，其中 A 是要编码的符号字母表（抱歉，无损标准应该包含在原始问题中）。如果 L < |A|那么我们就是在归类符号，从而丢失信息。当 L = |A|我们本质上拥有的是一个固定长度的可变代码，其中每个符号在我们的编码中具有相等的概率权重 table。既然我们知道了第一个问题的答案，那么第二部分的答案就更加简单了。 L 几乎可以是任何你想要的，只要它大于要编码的字母表的大小。通常我们希望 L 是 2 的幂以提高计算效率，然后我们希望 L 大于 |A|为了实现更好的压缩，所以一个非常常见的 L 大小是等于或大于字母表大小的 2 的最大幂的 2 倍。这可以很容易地通过这样的东西找到：
int alphabetSize = SizeOfAlphabet();
int L = pow(2, ceil(log(alphabetSize, 2)) + 1);