Shannon-Fano 编码是否有歧义？
Is Shannon-Fano coding ambiguous?
简而言之：
Fano 的论文 The Transmission of Information (1952) 中描述的 Shannon-Fano 编码 真的有歧义吗？
详细信息：
3篇论文
Claude E. Shannon 于 1948 年 7 月发表了他的著名论文 A Mathematical Theory of Communication。在这篇论文中，他发明了我们今天所知道的术语 bit他还定义了我们今天所说的 香农熵。并且他还在这篇论文中提出了一种基于熵的数据压缩算法。但是香农的算法太弱了，在某些情况下，“压缩”的消息可能比固定长度编码还要长。几个月后（1949 年 3 月）Robert M. Fano 在论文 The Transmission of Information 中发表了香农算法的改进版本。在 Fano 之后 3 年（1952 年 9 月），他的学生 David A. Huffman 在他的论文 A Method for the Construction of Minimum-Redundancy Codes 中发表了一个更好的版本。 霍夫曼编码比它的两个前身，至今仍在使用。但我的问题是关于 Fano 发布的算法，通常称为 Shannon-Fano-Coding.
算法
此描述基于 Wikipedia 中的描述。抱歉，我没有完整阅读 Fano 的论文。我只是浏览了一下。它有 37 页长，我真的很努力地想找到一段他谈到我的问题的主题，但我找不到。所以，这里是 Shannon-Fano 编码的工作原理：
- 计算每个字符在邮件中出现的频率。
- 按出现频率对所有字符排序，出现频率最高的字符在列表顶部
- 将列表分成两部分，使两部分的频率之和尽可能相等。将
0 位添加到一个部分，将 1 位添加到另一部分。
- 对包含 2 个或更多字符的每个部分重复步骤 3，直到所有部分仅包含 1 个字符。
- 连接所有回合的所有位。这是该字符的 Shannon-Fano 代码。
一个例子
让我们在一个非常小的示例上执行此操作（我认为这是出现问题的最小消息）。这是要编码的消息：
aaabcde
第 1 步和第 2 步生成两个表的前两列，如下所示。但如果维基百科对 Fanos 算法的解释是正确的，那么第 3 步就是模棱两可的。如果您在我的示例中应用此步骤，则有两种可能性将列表分成两部分（见下文）。这些可能性产生不同的代码，这些代码本身不值得一提。但关键是：两种可能性产生不同长度的代码。
可能性 1
如果有 2 种拆分列表的方法，使两个部分尽可能相等，则将那个字符放在拆分点（在我的示例中是字符 b ) 到包含low 频繁字符
的部分
+------+-------+-----+-----+-----+-----+-----+-----+------+
| | | 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 种拆分列表的方法，使两个部分尽可能彼此相等，则将位于拆分点的那个字符放到包含 high[ 的部分=80=] 频繁出现的字符
+------+-------+-----+-----+-----+-----+-----+-----+------+
| | | 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 编码是不明确的。
- 或者 Fano 在他的论文中添加了维基百科描述中缺失的另一个步骤？如果是这样的话：Fano 是如何解决这里描述的问题的？这两个版本中哪个版本与 Fano 的原始描述兼容？
为了直接回答您的问题，无需进一步详细说明如何打破平局，Shannon-Fano 的两种不同实现可能会为相同的输入生成不同长度的不同代码。
正如@MattTimmermans 在评论中指出的那样，Shannon-Fano 并不总是像霍夫曼编码那样产生最佳的 prefix-free 编码。因此，将其视为一种 算法 而更多地视为一种 启发式 可能会有所帮助 - 可能会产生好的代码但不是'不能保证给出最佳解决方案。许多启发式方法都会遇到类似的问题，即输入中的微小调整或关系的断开方式可能会导致不同的结果。一个很好的例子是 greedy coloring algorithm 用于查找图形的顶点着色。链接的维基百科文章包含一个示例，其中更改相同基本算法访问节点的顺序会产生截然不同的结果。
然而，即使是产生最佳结果的算法有时也会根据平局产生不同的最佳结果。以霍夫曼编码为例，它的工作原理是重复找到到目前为止组装的两棵 lowest-weight 树并将它们合并在一起。如果在某个中间步骤中有三棵或更多树都与相同的权重相关联，则霍夫曼编码的不同实现可能会产生不同的 prefix-free 代码，这些代码基于它们将它们连接在一起。不过，生成的树都同样“好”，因为它们都会产生相同长度的输出。 （这主要是因为，与 Shannon-Fano 不同，霍夫曼编码保证产生最佳编码。）
话虽这么说，但调整 Shannon-Fano 很容易，以便始终产生一致的结果。例如，您可以说“如果出现平局，请选择将较少项目放入顶部组的分区”，此时您始终会始终如一地生成相同的编码。它不一定是 最佳 编码，但是，话又说回来，因为从未保证 Shannon-Fano 会这样做，所以这可能不是主要问题。
另一方面，如果您对“当 Shannon-Fano 必须打破平局时，我如何决定如何打破平局以产生最佳解决方案？”这一问题感兴趣，然后我不确定除了递归地尝试这两个选项并查看哪个更好，这在最坏的情况下会导致 exponentially-slow 运行时间之外的方法。但也许这里的其他人可以找到一种方法>
准确的说是算法有歧义。通过阅读维基百科页面和原始论文的算法部分，我找不到任何关于它的提示。
实际上，为什么您会得到性能下降的解决方案？因为在可能性 2 中，你得到两个桶，频率为 3 和 1，即频率相当不同。
此问题已在论文（强调是我的）第 8 页中解决：
One may observe, however, that it will not generally be possible to
form groups equally likely to contain the desired message, because shifting
any one of the messages from one group to the other will change, by finite
amounts, the probabilities corresponding to the two groups.
不过对于法诺来说，这个问题并不是那么重要。他的目标不是定义一个非常简单实用的算法来压缩一些由几个字符组成的小消息。他对理论方面更感兴趣。为此，他正在考虑非常单独的长消息（这些单独的消息在您的示例中是字符）：
On the other hand, if the length of the messages is increased indefinitely, the accuracy with which the probabilities of the two groups can be made equal becomes better and better since the probability of each individual message approaches zero.
根据这个假设，您观察到的现象不太可能随着重要的性能下降而发生。
简而言之：
Fano 的论文 The Transmission of Information (1952) 中描述的 Shannon-Fano 编码 真的有歧义吗？
详细信息：
3篇论文
Claude E. Shannon 于 1948 年 7 月发表了他的著名论文 A Mathematical Theory of Communication。在这篇论文中，他发明了我们今天所知道的术语 bit他还定义了我们今天所说的 香农熵。并且他还在这篇论文中提出了一种基于熵的数据压缩算法。但是香农的算法太弱了，在某些情况下，“压缩”的消息可能比固定长度编码还要长。几个月后（1949 年 3 月）Robert M. Fano 在论文 The Transmission of Information 中发表了香农算法的改进版本。在 Fano 之后 3 年（1952 年 9 月），他的学生 David A. Huffman 在他的论文 A Method for the Construction of Minimum-Redundancy Codes 中发表了一个更好的版本。 霍夫曼编码比它的两个前身，至今仍在使用。但我的问题是关于 Fano 发布的算法，通常称为 Shannon-Fano-Coding.
算法
此描述基于 Wikipedia 中的描述。抱歉，我没有完整阅读 Fano 的论文。我只是浏览了一下。它有 37 页长，我真的很努力地想找到一段他谈到我的问题的主题，但我找不到。所以，这里是 Shannon-Fano 编码的工作原理：
- 计算每个字符在邮件中出现的频率。
- 按出现频率对所有字符排序，出现频率最高的字符在列表顶部
- 将列表分成两部分，使两部分的频率之和尽可能相等。将
0位添加到一个部分，将1位添加到另一部分。 - 对包含 2 个或更多字符的每个部分重复步骤 3，直到所有部分仅包含 1 个字符。
- 连接所有回合的所有位。这是该字符的 Shannon-Fano 代码。
一个例子
让我们在一个非常小的示例上执行此操作（我认为这是出现问题的最小消息）。这是要编码的消息：
aaabcde
第 1 步和第 2 步生成两个表的前两列，如下所示。但如果维基百科对 Fanos 算法的解释是正确的，那么第 3 步就是模棱两可的。如果您在我的示例中应用此步骤，则有两种可能性将列表分成两部分（见下文）。这些可能性产生不同的代码，这些代码本身不值得一提。但关键是：两种可能性产生不同长度的代码。
可能性 1
如果有 2 种拆分列表的方法，使两个部分尽可能相等，则将那个字符放在拆分点（在我的示例中是字符 b ) 到包含low 频繁字符
+------+-------+-----+-----+-----+-----+-----+-----+------+
| | | 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 种拆分列表的方法，使两个部分尽可能彼此相等，则将位于拆分点的那个字符放到包含 high[ 的部分=80=] 频繁出现的字符
+------+-------+-----+-----+-----+-----+-----+-----+------+
| | | 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 编码是不明确的。
- 或者 Fano 在他的论文中添加了维基百科描述中缺失的另一个步骤？如果是这样的话：Fano 是如何解决这里描述的问题的？这两个版本中哪个版本与 Fano 的原始描述兼容？
为了直接回答您的问题，无需进一步详细说明如何打破平局，Shannon-Fano 的两种不同实现可能会为相同的输入生成不同长度的不同代码。
正如@MattTimmermans 在评论中指出的那样，Shannon-Fano 并不总是像霍夫曼编码那样产生最佳的 prefix-free 编码。因此，将其视为一种 算法 而更多地视为一种 启发式 可能会有所帮助 - 可能会产生好的代码但不是'不能保证给出最佳解决方案。许多启发式方法都会遇到类似的问题，即输入中的微小调整或关系的断开方式可能会导致不同的结果。一个很好的例子是 greedy coloring algorithm 用于查找图形的顶点着色。链接的维基百科文章包含一个示例，其中更改相同基本算法访问节点的顺序会产生截然不同的结果。
然而，即使是产生最佳结果的算法有时也会根据平局产生不同的最佳结果。以霍夫曼编码为例，它的工作原理是重复找到到目前为止组装的两棵 lowest-weight 树并将它们合并在一起。如果在某个中间步骤中有三棵或更多树都与相同的权重相关联，则霍夫曼编码的不同实现可能会产生不同的 prefix-free 代码，这些代码基于它们将它们连接在一起。不过，生成的树都同样“好”，因为它们都会产生相同长度的输出。 （这主要是因为，与 Shannon-Fano 不同，霍夫曼编码保证产生最佳编码。）
话虽这么说，但调整 Shannon-Fano 很容易，以便始终产生一致的结果。例如，您可以说“如果出现平局，请选择将较少项目放入顶部组的分区”，此时您始终会始终如一地生成相同的编码。它不一定是 最佳 编码，但是，话又说回来，因为从未保证 Shannon-Fano 会这样做，所以这可能不是主要问题。
另一方面，如果您对“当 Shannon-Fano 必须打破平局时，我如何决定如何打破平局以产生最佳解决方案？”这一问题感兴趣，然后我不确定除了递归地尝试这两个选项并查看哪个更好，这在最坏的情况下会导致 exponentially-slow 运行时间之外的方法。但也许这里的其他人可以找到一种方法>
准确的说是算法有歧义。通过阅读维基百科页面和原始论文的算法部分，我找不到任何关于它的提示。
实际上，为什么您会得到性能下降的解决方案？因为在可能性 2 中，你得到两个桶，频率为 3 和 1，即频率相当不同。
此问题已在论文（强调是我的）第 8 页中解决：
One may observe, however, that it will not generally be possible to form groups equally likely to contain the desired message, because shifting any one of the messages from one group to the other will change, by finite amounts, the probabilities corresponding to the two groups.
不过对于法诺来说，这个问题并不是那么重要。他的目标不是定义一个非常简单实用的算法来压缩一些由几个字符组成的小消息。他对理论方面更感兴趣。为此，他正在考虑非常单独的长消息（这些单独的消息在您的示例中是字符）：
On the other hand, if the length of the messages is increased indefinitely, the accuracy with which the probabilities of the two groups can be made equal becomes better and better since the probability of each individual message approaches zero.
根据这个假设，您观察到的现象不太可能随着重要的性能下降而发生。