简而言之：
Fano的论文《信息的传输》(1952)中描述的Shannon Fano编码真的很模糊吗？
详细信息：
3篇论文
Claude E.Shannon于1948年7月发表了他的著名论文《沟通的数学理论》。在这篇论文中，他发明了我们今天所知的术语bit，他还定义了我们今天称之为Shannon熵的术语。他还在本文中提出了一种基于熵的数据压缩算法。但是Shannon的算法太弱了，以至于在某些情况下；压缩的"；消息可能比固定长度编码更长。几个月后(1949年3月)，Robert M.Fano在论文《信息的传递》中发表了Shannons算法的改进版本。法诺3年后(1952年9月)，他的学生大卫·A·霍夫曼在他的论文《最小冗余码的构造方法》中发表了一个更好的版本Hoffman编码比它的两个前代更有效，并且至今仍在使用。但我的问题是关于Fano发布的算法，通常被称为Shannon Fano编码
算法
此描述基于维基百科中的描述。对不起，我没有完全阅读法诺的论文。我只浏览了一下。它有37页长，我真的很努力地想找到一段他谈论我问题主题的文章，但我找不到。所以，以下是Shannon Fano编码的工作原理：
- 计算每个字符在消息中出现的频率
- 按频率对所有字符进行排序，列表顶部频率最高的字符
- 将列表分为两部分，使两部分的频率之和尽可能相等。将比特
0添加到一个部分，将比特1添加到另一部分 - 对包含2个或多个字符的每个部分重复步骤3，直到所有部分仅包含1个字符
- 连接所有轮次中的所有位。这是那个角色的Shannon Fano密码
示例
让我们在一个非常小的示例上执行此操作(我认为这是出现问题的最小消息)。这是要编码的消息：
aaabcde
步骤1和2生成下面所示的两个表的前2列。但如果维基百科对Fanos算法的解释是正确的，那么第三步就不明确了。如果将此步骤应用于我的示例，则有两种可能性可以将列表拆分为两部分(见下文)。这些可能性产生了不同的代码，这些代码本身就不值得提及。但关键是：这两种可能性产生不同长度的代码
可能性1
如果有两种方法可以拆分列表，使两个部分尽可能相等，那么将位于拆分点的字符(在我的示例中是字符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
如果有两种方法可以拆分列表，使两个部分尽可能相等，则将位于拆分点的字符放在包含高频繁字符的部分
+------+-------+-----+-----+-----+-----+-----+-----+------+
| | | 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
所以，它长了一点。
所以，以下是我的问题：
- 维基百科对Shannon Fano编码的描述真的正确和完整吗？如果是这种情况，那么Shannon Fano编码是模棱两可的
- 或者法诺在他的论文中添加了维基百科描述中缺失的另一个步骤？如果是这样的话：法诺是如何解决这里描述的问题的？这两个版本中的哪一个与法诺的原始描述兼容
算法中确实存在歧义。通过阅读维基百科页面和原始论文的算法部分，我找不到任何关于它的提示。
在实践中，为什么会得到性能下降的解决方案？因为在可能性2中，你会得到两个桶，频率分别为3和1，也就是说频率不同。
这个问题在第8页的论文中得到了解决(重点是我的)：
然而，人们可能会发现表单组同样可能包含所需的消息，因为从一组到另一组的任何一条消息都将通过有限数量，对应于这两组的概率。
但对于法诺来说，这个问题并不那么重要。他的抱负不是定义一个非常简单实用的算法来压缩一些由几个字符组成的小消息。他对理论方面更感兴趣。为此，他正在考虑非常单独的长消息(在您的示例中，这些单独的消息是字符)：
另一方面，如果消息的长度无限期地增加，则由于每个单独消息的概率接近零，使得两组概率相等的准确性变得越来越好。
有了这个假设，您观察到的现象不太可能随着重要的性能下降而发生。
要直接回答您的问题，而无需进一步阐述如何打破联系，Shannon Fano的两种不同实现可以为相同的输入生成不同长度的不同代码。
正如@MattTimmermans在评论中指出的那样，Shannon Fano并不总是像霍夫曼编码那样产生最佳的无前缀编码。因此，少把它看作是算法，多把它看作启发式可能会产生好的代码，但不能保证给出最佳解决方案，这可能会有所帮助。许多启发式算法都遇到了类似的问题，在这些问题中，输入中的微小调整或如何打破联系可能会导致不同的结果。这方面的一个很好的例子是用于查找图的顶点着色的贪婪着色算法。维基百科的链接文章包括一个例子，在这个例子中，改变相同基本算法访问节点的顺序会产生截然不同的结果。
然而，即使是产生最佳结果的算法，有时也会根据决胜局产生不同的最佳结果。以霍夫曼编码为例，它的工作原理是反复找到迄今为止组装的两个权重最低的树，并将它们合并在一起。如果在某个中间步骤中有三个或更多的树都被绑定到相同的权重，则霍夫曼编码的不同实现可以基于它们连接在一起的两个来产生不同的无前缀代码。所得到的树都将是相等的"树"；好，"；不过，因为它们都会产生相同长度的输出。(这在很大程度上是因为，与Shannon Fano不同，霍夫曼编码可以保证产生最佳编码。)
也就是说，调整Shannon Fano很容易，这样它总是能产生一致的结果。例如，你可以说"；在平局的情况下，选择将较少项目放入顶部组的分区；在这一点上，您将始终一致地生成相同的编码。这不一定是最佳编码，但话说回来，由于Shannon Fano从未保证会这样做，这可能不是一个主要问题。
另一方面，如果你对"；当Shannon Fano必须打破平局时，我如何决定如何打破平局以产生最佳解决方案"那么我不确定有什么方法可以做到这一点，除了递归地尝试这两个选项，看看哪一个更好，在最坏的情况下，这会导致运行时间呈指数级缓慢。但也许这里的其他人可以找到一种方法>