🔢 mathematics

Asymmetric Encoding-Decoding Schemes for Lossless Data Compression

本文提出了非对称编解码方案（AEDS），这是一种通用的无损压缩方法，其通过逆向编码数据并正向解码数据，证明了在特定概率分布下其性能可以优于哈夫曼编码，并且随着状态数量的增加，其收敛至信源熵的速率为 $O(1/N)$ 。

原作者： Hirosuke Yamamoto, Ken-ichi Iwata

发布于 2026-01-26

📖 1 分钟阅读🧠 深度阅读

原作者： Hirosuke Yamamoto, Ken-ichi Iwata

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你正试图为一个旅行装满衣服的行李箱打包。无损数据压缩的目标是尽可能多地装入物品，同时占用最小的空间，且不丢失任何一件物品。

几十年来，两种最著名的“打包方法”分别是 哈夫曼编码 (Huffman coding) 和 算术编码 (Arithmetic coding)。

哈夫曼编码 就像一个聪明的整理员，为常见的物品分配短标签，为稀有的物品分配长标签。它既快速又可靠。
算术编码 就像一位数学大师，将物品挤压进一个极小的、连续的空间中。它极其高效，但需要繁重的脑力计算来进行这种挤压。

最近，一种名为 tANS (表格化非对称数值系统) 的方法出现了。它是一个混合体：它拥有算术编码的高效性，但通过使用查找表（类似于“小抄”）来存储答案，从而避免了每次都进行繁重的数学运算。它既快又非常高效。

问题在于： 即便是 tANS 也有极限。它是建立在一套特定的规则之上的，就像一个具有固定隔层的行李箱。有时，你正在打包的“衣服”（数据）并不完美契合这些预设的隔层，从而留下了一点点浪费的空间。

解决方案：AEDS (非对称编解码方案)
这篇论文介绍了一种更灵活的打包方法，称为 AEDS。你可以把 AEDS 想象成一个“超级行李箱”，它是对 tANS 的一种泛化。它保留了旧方法的最优特性，同时打破了僵化的规则，允许更广泛的多样化打包策略。

以下是它的工作原理，使用简单的类比说明：

1. “倒序打包，正序拆解”的技巧

大多数打包方法都是按顺序进行的：先打包物品 1，然后是物品 2，最后是物品 3。

AEDS (以及 tANS) 做了一些奇怪的操作：它们倒着打包行李箱（先物品 3，然后 2，最后 1），但正着拆解行李箱（先物品 1，然后 2，最后 3）。
为什么？ 想象你在搭建积木塔。如果你从上往下搭建，你可以用一个简单的数字来记录整座塔的高度。如果你从下往上搭建，你需要复杂的计算才能知道还剩多少空间。通过倒着打包，AEDS 可以使用一个单一的“计数器”来管理整个序列，这使得它极其高效。

2. “状态机”（交换机台）

在旧的方法中，打包的“规则”是固定的。在 AEDS 中，规则会根据一个状态 (state) 而改变。

想象一个拥有许多指示灯（状态）的交换机台。
当你打包一个物品时，你会观察当前哪盏灯亮着。这盏灯会告诉你如何为该物品打标签，以及下一步要切换到哪盏灯。
因为 AEDS 允许任何模式的灯光和切换（而不局限于 tANS 所允许的特定模式），它可以为数据找到“完美的契合点”，而这正是 tANS 难以处理的地方。

3. AEDS 何时胜出？

论文证明了 AEDS 在特定场景下是“强力增压器”：

“优势项”场景： 假设你的行李箱里大部分都是同一种类型的物品（例如，62% 的衣服都是 T 恤）。
- 标准的哈夫曼编码表现不错，但仍会留下一个小间隙。
- AEDS 可以重新排列打包规则，将那个优势项挤压得更紧凑。论文显示，如果其中一项数据占比超过 61.8%，一个简单的 2 状态 AEDS 就能击败哈夫曼编码。如果你使用 5 个状态，即使该项数据占比仅为 57%，它也能胜过哈夫曼编码。
“均匀分布”场景： 假设你有等量的各种类型的物品（就像一副扑克牌）。
- 标准方法会因为无法完美分割空间而产生微小的“浪费空间”（冗余）。
- AEDS 可以专门为这种均匀混合物构建一个定制的“交换机台”，从而显著减少这种浪费空间，有时几乎可以消除它。

4. “速度与智能”的平衡

论文强调了一个关键的权衡：

哈夫曼 很快，但体积不是最小的。
算术编码 体积最小，但很慢（数学运算太多）。
AEDS 旨在寻找“金发姑娘区”（即最理想的中庸之道）：它像哈夫曼一样快（因为它使用简单的查找表而非繁重计算），但可以像最好的理论极限一样小。

核心结论

作者们开发了一种新的“打包算法” (AEDS)，它是流行方法 tANS 的更灵活版本。

它是向后兼容的： 它可以完成 tANS 能做的所有事情。
它更聪明： 对于某种物品非常常见或物品分布均匀的数据，它可以找到更好的打包安排。
它是可扩展的： 随着你给系统更多的“状态”（即更多的交换机开关），它会越来越接近理论上的完美大小，最终达到数据压缩所能达到的绝对极限。

简而言之，AEDS 是一种新的数据组织方式，它利用巧妙的“倒序”技巧和灵活的规则，将信息压缩到比以往更小的空间中，且不会降低计算机的速度。

技术摘要：用于无损数据压缩的非对称编解码方案

问题陈述

本文探讨了传统无损数据压缩算法（特别是哈夫曼编码和算术编码）的局限性。哈夫曼编码虽然简单，但在压缩率方面往往并非最优；而算术编码虽然能达到接近熵值的性能，却需要复杂的算术运算。非对称数值系统（ANS），特别是表格式 ANS（tANS），通过使用单个整数变量和查找表提供了一种高速替代方案，它采用逆序编码和正序解码。然而，tANS 所代表的理论代码类别相对较窄。本文旨在推广 tANS 框架，以创建一类更广泛的代码，这些代码在特定条件下能够实现比哈夫曼编码更短的平均码长，同时保持基于表法计算的高效性。

方法论

作者提出了一种新的编码框架，称为非对称编解码方案（AEDS）。该方案通过放宽对状态转移和码字分配的约束，实现了对 tANS 的推广。

tANS 的推广：
- AEDS 结构： AEDS 利用有限的状态集 $X$ $X$ 。与依赖于区间划分派生的特定算术映射的 tANS 不同，AEDS 通过任意函数定义编码和解码过程：
  - 编码： 将源符号 $s$ 和状态 $\hat{x}$ 映射到码字 $\beta$ 和新状态 $x$ （逆向转移）。
  - 解码： 将码字 $\beta$ 和状态 $x$ 映射到源符号 $s$ 和新状态 $\hat{x}$ （正向转移）。
- 非对称性： 该方案以逆序（ $s_n \to s_1$ ）对序列进行编码，并以正序（ $s_1 \to s_n$ ）进行解码，这与 ANS 类似，但不需要算术运算。
- 灵活性： 编码码字集不需要是前缀自由的，且解码源符号集不需要对于每个状态都覆盖所有源符号，这允许构建更灵活的代码树。
通过代码树构建：
本文展示了如何基于任意前缀自由代码树（例如哈夫曼树）来构建 AEDS。文中引入了两种特定类型：
- Type-I AEDS： 基于代码树 $T$ 构建，包含 $N$ 个状态。它利用“相位引入码”（针对均匀分布的哈夫曼码）来优化特定状态转移下的平均码长。
- Type-II AEDS： 一种具有 5 个状态的构造方式，旨在当代码树根节点的概率权重低于 Type-I 所需阈值时提高性能。
状态划分 AEDS (sAEDS)：
为了便于理论分析并建立界限，作者定义了一个受限的子类，称为 sAEDS。在 sAEDS 中，状态空间 $X$ 被划分为与每个源符号 $s$ 相对应的互斥集合 $X_s$ 。这种结构确保了对于任何状态 $x \in X_s$ ，解码函数 $D_x$ 始终输出 $s$ ，从而简化了对平稳概率和平均码长的分析。

主要贡献与结果

1. 优于哈夫曼编码

本文推导出了 AEDS 在 i.i.d.（独立同分布）信源下实现比标准哈夫曼编码更短平均码长的条件：

Type-I AEDS（2 状态）： 如果哈夫曼码树中根节点的子节点概率权重 $P_R > \omega^{(I)} \approx 0.61803$ ，则具有 2 个状态的 Type-I AEDS 比哈夫曼编码具有更短的平均码长。
Type-II AEDS（5 状态）： 如果 $P_R > \omega^{(II)} \approx 0.56984$ ，则具有 5 个状态的 Type-II AEDS 性能优于哈夫曼编码。
均匀信源： 对于均匀分布的信源，本文表明，基于非哈夫曼代码树（特别是能够最大化子树概率权重的树）构建 AEDS，可以进一步降低比基于哈夫曼树构建的 AEDS 更低的平均码长。

2. 理论界限与收敛性

作者推导了 sAEDS 的平均码长上界，这些界限同样适用于 tANS：

上界： 平均码长 $L$ 受限于 $L \le H(p) + D(p \| q) + \sigma$ ，其中 $H(p)$ 是信源熵， $D(p \| q)$ 是信源分布与状态分布之间的相对熵， $\sigma \approx 0.08607$ 。
收敛速率： 对于具有 $N$ 个状态的最优 AEDS（及 tANS），其平均码长随 $N$ 的增加以 $O(1/N)$ 的速度收敛至信源熵 $H(p)$ 。这证明了增加状态数可以系统性地减少冗余。

3. 最坏情况冗余分析

本文分析了二进制信源和均匀信源的最坏情况冗余。研究表明，当信源分布偏斜（例如一个符号具有高概率）时，Type-I 和 Type-II AEDS 可以实现比哈夫曼编码显著更低的最坏情况冗余。

意义与主张

本文声称 AEDS 是 tANS 的一种推广，并且具有更广泛的代码类别。其主要意义在于：

性能提升： 证明了简单的基于状态的方案（仅需 2 或 5 个状态）在特定的概率条件下，在理论上可以超越作为长期基准的哈夫曼编码。
理论统一： 提供了一个统一的框架（sAEDS），它涵盖了 tANS 并允许进行严格的信息论分析，包括推导向熵收敛的速率（ $O(1/N)$ ）。
实际可行性： 强调了与 tANS 一样，AEDS 可以使用查找表实现，无需复杂的算术运算，这使得它们在提供优于哈夫曼编码的潜在压缩增益的同时，仍适用于高速实际系统。

作者指出，虽然该构造在理论上是完善的且提供了压缩增益，但存储复杂度（空间复杂度）可能会随着状态数的增加而增加，不过他们建议对于特定的构造（如基于哈夫曼树的 Type-I 和 Type-II），其复杂度可以控制在与哈夫曼编码相当的水平。