🔢 mathematics

Pareto-type finite-block optimality for source codes: a constrained Markov example

本文证明，针对特定四符号约束马尔可夫源的可逆 Dalai-Leonardi 码在有限块平均长度方面并非帕累托最优，因为新构建的规范单射码对所有块长 $n \ge 2$ 均实现了严格更低的期望块长。

原作者： Stefano Della Fiore

发布于 2026-05-06

📖 1 分钟阅读🧠 深度阅读

原作者： Stefano Della Fiore

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

想象你正在经营一家邮局，但有一条非常具体的规则：你只能发送符合特定模式的信件。也许你的城镇只允许发送以"A"或"B"开头、且对其后跟随的字母有特定规则的信件。这就是论文中所称的“受限信源”。

在数据压缩（高效发送信息）的世界里，目标通常是将这些字母转换为尽可能短的 0 和 1 字符串（二进制代码）。

旧方法与新思路

长期以来，科学家们有一种衡量代码优劣的标准方法。他们会查看海量字母的代码“平均长度”。如果你发送了 1,000 封信件，他们会检查平均大小。如果平均值较低，该代码就被认为是“好”的。

然而，这篇论文提出了一个不同且更细致的问题：如果我们观察“每一步”会怎样？

想象两位送货司机：司机 D（老牌、成熟的司机）和司机 S（新型、实验性的司机）。

司机 D 的路线平均每封信耗时正好 1.5 分钟。
司机 S 正试图变得更聪明。

论文问道：司机 D 是否是我们能做到的绝对最佳？还是存在一位司机 S，他“从未比司机 D 慢”，但在某些特定时刻“更快”？

用数学术语来说，这被称为“帕累托最优”。如果司机 S 从未更慢且有时更快，那么司机 D 就不再是“最佳”选择。

实验：一个四字母的城镇

作者斯特凡诺·德拉·菲奥雷（Stefano Della Fiore）利用一个包含四个字母 A、B、C 和 D 的“城镇”建立了一个测试案例。

规则如下：
- 如果你有一个"A"，下一个字母必须是 A 或 C。
- 如果你有一个"B"，下一个字母必须是 B 或 D。
- 如果你有一个"C"或"D"，下一个字母可以是任何字母（A、B、C 或 D）。

这创造了一组特定的“允许”单词。作者采用了一个由达莱（Dalai）和莱昂纳迪（Leonardi）创建的著名代码（我们称之为“达莱 - 莱昂纳迪代码”），该代码已知对此城镇非常高效。它平均每封信正好占用 1.5 位（信息单位）。

新策略："Shortlex"排序

作者创建了一个新代码，我们称之为"Shortlex 代码”。其工作原理如下，使用一个简单的类比：

想象你有一份该城镇中所有允许单词的巨型列表。你想为它们分配唯一的二进制代码（如 0、1、00、01、10 等）。

按“成本”排序： 首先，你根据单词的“惊讶程度”对它们进行排序。非常常见的单词成本低；罕见的单词成本高。
按长度排序： 如果两个单词成本相同，你将较短的那个排在前面。
按字母顺序排序： 如果仍然平局，则按字母顺序排列。
分配代码： 然后你按顺序分发二进制代码：第一个单词得"0"，第二个得"1"，第三个得"00"，依此类推。

这就是"Shortlex 代码”。这是一种非常合乎逻辑、具有“规范性”的做法。

重大发现

作者运行数据后发现了一些令人惊讶的结果：

对于单个字母（n=1）： 新代码与旧代码完全一样好。它们打平。
对于两个或更多字母（n≥2）： 新代码“严格更优”。它节省了空间。

论文证明，对于任何大于一个字母的字母块，新代码的平均长度总是比著名的达莱 - 莱昂纳迪代码更短。

“一位”的魔力

为什么会发生这种情况？论文使用了一些复杂的数学来解释，但核心思想是系统中存在一个“缺口”。

将二进制代码想象成剧院里的座位。

旧代码（达莱 - 莱昂纳迪）填充座位的方式留下了一些本可用于节省空间的空位，但它不知道如何为小群体高效利用它们。
新代码（Shortlex）就像一位聪明的引座员，他意识到对于具有特定“成本”的每组单词，恰好有一半可以挤进稍小的座位（节省 1 位），而另一半则占用正常座位。

因为新代码足够聪明，能够至少有一半的时间（实际上对于 2 个或更多字母的组，超过一半的时间）抓住那个“更小的座位”，所以它每次都能节省一点点空间。

结果：微小但真实的胜利

论文精确计算了节省了多少空间。

旧代码对于 n 个字母需要 $1.5 \times n$ 位。
新代码需要的略少： $1.5 \times n$ 减去一个随着 n 增大而变小的微小分数（具体来说，它节省了约 $1/\sqrt{n}$ 位）。

结论：
著名的达莱 - 莱昂纳迪代码，曾被认为是这种特定类型受限信源的黄金标准，并非绝对最佳。新的"Shortlex"代码在除第一个步骤之外的每一步都击败了它。

为什么这很重要（根据论文）

论文并不声称这明天就能修复你的 Wi-Fi 或压缩你的照片。相反，它提出了一个理论观点：

在数据压缩领域，我们通常关注长期的“平均”性能。
这篇论文表明，如果你观察“每一步”（有限块最优性），你可以找到比我们之前认为的最优代码严格更优的代码。
它证明了对于受限信源（数据遵循特定规则），通过仔细观察我们如何排列代码，可以发现隐藏的“帕累托”优势。

简而言之：旧冠军实际上并非不可战胜；一位新挑战者找到了一种方法，在除第一场之外的每一场比赛中都比它更快。

技术摘要：源码的 Pareto 型有限块最优性

问题陈述
本文研究了在源约束下，单射源码的有限块最优性概念。经典的源编码理论（例如香农、克拉夫特、麦克米伦）侧重于渐近熵界和与源无关的唯一可解码性，而本研究关注的是源生成受限语言（所有可能字符串的子集）的场景。在此类设定中，编码只需在源生成的可接受字符串集合上唯一可解码，而不必在所有可能的二进制拼接上唯一可解码。

核心问题在于：给定的可逆（单射）码相对于期望块长度序列是否是Pareto 最优的？具体而言，对于同一受限源的两个单射码 $C$ 和 $\tilde{C}$ ，是否存在一个码支配另一个，使得对于所有块长度 $n \ge 1$ ，均有 $E[|C(X_1^n)|] \le E[|\tilde{C}(X_1^n)|]$ ，且对至少一个 $n$ 严格不等式成立？本文使用 Dalai 和 Leonardi 引入的四符号受限马尔可夫源作为测试案例。他们现有的可逆码对于块长度 $n$ 实现了恰好 $3n/2$ 的期望长度，而块熵为 $3n/2 + 1/2$ 。作者询问该基准是否是 Pareto 最优的，或者是否存在更优越的单射码。

方法论
作者在可接受字符串集合 $\mathcal{A}$ 上构建了一个规范单射二进制映射 $C: \mathcal{A} \to \{0, 1\}^+$ 。构建过程如下：

排序：可接受字符串按递增的信息成本 $K(u) = -\log_2 P(X_1^m = u)$ 排序，其次按字符串长度排序，最后按字典序排序。
分配：字符串按短字典序（shortlex order，即先按长度排序，再按字典序排序）映射到非空二进制字符串。

分析依赖于按信息成本对可接受字符串的组合枚举。利用了该特定马尔可夫源的关键结构性质：

二值概率：所有可接受块的概率均为 2 的幂，使得信息成本 $K(u)$ 为整数。
成本递推：成本为 $k$ 的可接受字符串数量 $S_k$ 满足线性递推关系 $S_k = S_{k-1} + 2S_{k-2}$ 。
短字典序间隙恒等式：证明了一个关键组合恒等式，表明对于任何成本类 $k$ ，成本小于 $k$ 的可接受字符串数量恰好留下了长度为 $k-1$ 的可用二进制字符串的一半未被使用。因此，在任何成本类 $k$ 内，恰好有一半的字符串获得长度为 $k-1$ 的码，另一半获得长度为 $k$ 的码。

概率分析将长度为 $n$ 的块的信息成本视为源自二项统计的随机变量 $K_n$ 。作者定义了一个“节省指示器” $I_n$ ，当码长为 $K_n - 1$ 时其值为 1，否则为 0。期望长度表示为 $E[|C(X_1^n)|] = E[K_n] - P(I_n = 1)$ 。

主要贡献与结果

统一改进：本文证明，对于 Dalai–Leonardi 源，规范码 $C$ 满足：
$E[|C(X_1^n)|] \le \frac{3}{2}n$
对所有 $n \ge 1$ 成立，且等式仅在 $n=1$ 时成立。对于所有 $n \ge 2$ ，不等式是严格的。这表明 Dalai–Leonardi 码并非 Pareto 最优；所提出的规范码从未表现得更差，且对于每个块长度 $n \ge 2$ 表现严格更优。
渐近增益：作者推导了改进量的定量渐近界。对于任意固定常数 $c < \frac{\sqrt{2}}{18\sqrt{\pi}}$ ，存在一个 $n_0$ ，使得对于所有 $n \ge n_0$ ：
$E[|C(X_1^n)|] \le \frac{3}{2}n - \frac{c}{\sqrt{n}}$
这确立了相对于 Dalai–Leonardi 基准的阶为 $O(n^{-1/2})$ 的有限块增益。
概率机制：证明表明，对于所有 $n \ge 2$ ，获得较短码长（ $K_n - 1$ ）的概率严格大于 $1/2$ 。具体而言， $P(I_n = 1) \ge 1/2$ ，且对于 $n \ge 2$ 严格不等式成立。这种“一位节省”在每个块长度上发生的概率至少为 $1/2$ ，这是由可接受字符串在成本类中的特定分布以及短字典序排序所驱动的。

意义
本文声称提供了一个具体且完全可分析的示例，证明源约束可以产生有限块增益，如果仅依赖熵或与源无关的唯一可解码性，这些增益将是不可见的。通过将基准要求从“与源无关的唯一可解码性”转变为“在可接受语言上的单射性”，该工作揭示了可逆构造可以被优化，以实现有限块平均长度的 Pareto 改进。该示例被描述为简单但足以展示受限条件下单射源编码所需的自然有限块 Pareto 比较。结果表明，受限源的标准可逆码即使在熵方面看似最优，在有限块意义上也可能并非最优。