Shannon-Fano 编码是否有歧义？

Question

简而言之：

Fano 的论文信息传输（1952 年）中描述的Shannon-Fano 编码真的很模糊吗？

详细信息：

3 篇论文
克劳德·E·香农 (Claude E. Shannon) 于 1948 年 7 月发表了他的著名论文通信数学理论。在这篇论文中，他发明了我们今天所知的术语位，并且还定义了我们今天所知道的术语位。今天调用香农熵。他还在本文中提出了一种基于熵的数据压缩算法。但香农的算法太弱了，在某些情况下，“压缩”的消息可能比固定长度编码的消息还要长。几个月后（1949 年 3 月）Robert M. Fano 在论文

算法
此描述基于 Wikipedia< 的描述< /a>.抱歉，我没有完全阅读法诺的论文。我只是浏览了一下。它有37页长，我真的很努力地想找到一段他谈论我的问题主题的段落，但我找不到。因此，香农-法诺编码的工作原理如下：

1. 计算每个字符在消息中出现的频率。
2. 按频率对所有字符进行排序，频率最高的字符位于列表顶部
3. 将列表分为两部分，使两部分的频率总和尽可能相等。将位 0 添加到一个部分，将位 1 添加到另一部分。
4. 对包含 2 个或更多字符的每个部分重复步骤 3，直到所有部分仅包含 1 个字符。
5. 连接所有轮次的所有位。这是该字符的香农法诺代码。

一个例子
让我们在一个非常小的示例上执行此操作（我认为这是出现问题的最小消息）。以下是要编码的消息：

aaabcde

步骤 1 和 2 生成如下所示的两个表的前 2 列。但如果维基百科对 Fanos 算法的解释是正确的，那么第 3 步是不明确的。如果您在我的示例中应用此步骤，则有两种可能性将列表分为两部分（见下文）。这些可能性产生不同的代码，其本身不值得一提。但要点是：这两种可能性会产生不同长度的代码。

---

可能性 1

如果有 2 种方法来分割列表，使两个部分尽可能彼此相等，则放置该字符，位于分割点（在我的示例中是字符 b）到包含低频繁字符的部分

+------+-------+-----+-----+-----+-----+-----+-----+------+
|      |       |   round1  |   round2  |   round3  |      |
| char | frequ | sum | bit | sum | bit | sum | bit | code |
+------+-------+-----+-----+-----+-----+-----+-----+------+
|   a  |   3   |  3  |  0  |                       | 0    |
|      |       +-----+-----+-----+-----+-----+-----+------+
|   b  |   1   |     |     |     |     |  1  |  0  | 100  |
|      |       |     |     |  2  |  0  +-----+-----+------+
|   c  |   1   |     |     |     |     |  1  |  1  | 101  |
|      |       |  4  |  1  +-----+-----+-----+-----+------+
|   d  |   1   |     |     |     |     |  1  |  0  | 110  |
|      |       |     |     |  2  |  1  +-----+-----+------+
|   e  |   1   |     |     |     |     |  1  |  1  | 111  |
+------+-------+-----+-----+-----+-----+-----+-----+------+

编码的消息是

000100101110111  length = 15 bit
aaab  c  d  e

---

可能性 2

如果有 2 种分割方式该列表使得两个部分彼此相等可能的话，那么将位于分裂点的那个字符放到包含高频繁字符的部分

+------+-------+-----+-----+-----+-----+-----+-----+------+
|      |       |   round1  |   round2  |   round3  |      |
| char | frequ | sum | bit | sum | bit | sum | bit | code |
+------+-------+-----+-----+-----+-----+-----+-----+------+
|   a  |   3   |     |     |  3  |  0  |           | 00   |
|      |       |  4  |  0  +-----+-----+           +------+
|   b  |   1   |     |     |  1  |  1  |           | 01   |
|      |       +-----+-----+-----+-----+-----+-----+------+
|   c  |   1   |     |     |     |     |  1  |  0  | 100  |
|      |       |     |     |  2  |  0  |-----+-----+------+
|   d  |   1   |  3  |  1  |     |     |  1  |  1  | 101  |
|      |       |     |     +-----+-----+-----+-----+------+
|   e  |   1   |     |     |  1  |  1  |           | 11   |
+------+-------+-----+-----+-----+-----+-----+-----+------+

编码消息是

0000000110010111  length = 16 bit
a a a b c  d  e

所以，它长了一位。

---

所以，我的问题是：

• 维基百科对香农法诺编码的描述真的正确和完整吗？如果是这种情况，那么香农-法诺编码就是不明确的。
• 或者法诺在他的论文中添加了维基百科描述中缺少的另一个步骤？如果是这种情况：Fano 是如何解决这里描述的问题的？这两个版本中哪一个与 Fano 的原始描述兼容？

Answer 1

确切地说，算法中存在二义性。通过阅读维基百科页面和原始论文的算法部分，我找不到任何关于它的提示。

在实践中，为什么您会得到性能下降的解决方案？因为在可能性 2 中，您会得到两个桶，频率为 3 和 1，即频率相当不同。

这个问题在论文第 8 页中得到了解决（强调是我的）：

但是，人们可能会发现，通常不可能
形成同样可能包含所需信息的组，因为转移
从一组到另一组的任何一条消息都会发生有限的变化
金额，对应于两组的概率。

但对于法诺来说，这个问题并不是那么重要。他的野心不是定义一个非常简单实用的算法来压缩一些由几个字符组成的小消息。他对理论方面更感兴趣。为此，他正在考虑非常单独的长消息（这些单独的消息是您示例中的字符）：

另一方面，如果消息的长度无限增加，则使两组概率相等的准确性会变得越来越好，因为每条消息都接近于零。

根据这个假设，您观察到的现象不太可能发生，并且性能会显着下降。

Answer 2

为了直接回答您的问题，无需进一步详细说明如何打破联系，香农法诺的两种不同实现可以为相同的输入生成不同长度的不同代码。

正如 @MattTimmermans 在评论中指出的那样，Shannon-Fano 并不总是像霍夫曼编码那样产生最佳的无前缀编码。因此，将其视为一种算法，而更多地启发式可能会有所帮助 - 可能会产生良好的代码，但不能保证给出最佳的结果解决方案。许多启发式方法都遇到类似的问题，其中输入的微小调整或关系的打破方式可能会导致不同的结果。一个很好的例子是用于查找图的顶点着色的贪婪着色算法。链接的维基百科文章包括一个示例，其中更改相同基本算法访问节点的顺序会产生截然不同的结果。

然而，即使是产生最佳结果的算法有时也会根据抢七局产生不同的最佳结果。以霍夫曼编码为例，它的工作原理是反复查找迄今为止组装的两个权重最低的树并将它们合并在一起。如果在某个中间步骤中有三棵或更多树都被绑定到相同的权重，则霍夫曼编码的不同实现可能会根据它们连接在一起的两棵树产生不同的无前缀代码。不过，生成的树都同样“好”，因为它们都会产生相同长度的输出。 （这主要是因为，与 Shannon-Fano 不同，霍夫曼编码保证产生最佳编码。）

话虽如此，很容易调整 Shannon-Fano，使其始终产生一致的结果。例如，您可以说“如果出现平局，请选择将较少项目放入顶部组的分区”，此时您将始终一致地生成相同的编码。它不一定是最佳编码，但话又说回来，由于 Shannon-Fano 从未保证这样做，因此这可能不是一个主要问题。

另一方面，如果您对“当 Shannon-Fano 必须打破平局时，我如何决定如何打破平局以产生最佳解决方案？”的问题感兴趣，那么我不确定除了递归地尝试这两个选项并查看哪个更好之外，还有一种方法可以做到这一点，这在最坏的情况下会导致运行时间呈指数级缓慢。但也许这里的其他人可以找到一种方法来做到这一点>