我试图解决一些霍夫曼编码问题，但我总是得到不同的码字值（值而不是长度）。例如，如果字符 'c' 的码字是 100，在我的解决方案中它是 101。
下面是一个例子：
字符频率码字我的解决方案 一个 22 00 10 乙 12 100 010 24 01 11 D 6 1010 0110 E 27 11 00 传真 9 1011 0111
两种解决方案的码字长度相同，并且不存在作为另一个码字前缀的码字。
这是否使我的解决方案有效？或者它必须只有 2 个解决方案，最佳的一个并翻转最佳的位？
有 96 种可能的方法可以将 0 和 1 分配给那组长度，并且所有方法都是完全有效的、最佳的前缀代码。你已经展示了其中的两个。
存在定义解决歧义的“规范”霍夫曼代码的约定。定义规范代码的价值在于将代码从压缩器传输到解压缩器。只要双方都知道并同意如何明确分配 0 和 1，那么只需要传输每个符号的代码长度——而不是代码本身。
该deflate格式以零开始争取在最短的代码，并增加了。在每个代码长度内，代码按符号值排序，即按符号排序。因此，对于您的代码，规范的霍夫曼代码将是：
A - 00
C - 01
E - 10
B - 110
D - 1110
F - 1111
因此，两个位代码按符号顺序 A、C、E 分配，类似地，四个位代码按 D、F 顺序分配。较短的代码在较长的代码之前分配。
在寻找代码长度时会出现不同且有趣的歧义。根据等频节点的组合顺序，即当您可以选择两个以上的最低频率节点时，您实际上可以得到完全相同最优的不同代码长度集。即使代码长度不同，当您将长度乘以频率并将它们相加时，您会得到两个不同代码的完全相同的位数。
同样，不同的代码都是最优的并且同样有效。在选择要组合的节点时，也有一些方法可以解决这种歧义，这样做的好处是可以最小化树的深度。这可以减少表驱动霍夫曼解码的表大小。
例如，考虑频率 A: 2, B: 2, C: 1, D: 1。你首先将 C 和 D 结合起来得到 2。然后你有 A、B 和 C+D 都具有频率 2。现在你可以选择组合 A 和 B，或 C+D 与 A 或 B。这给出了两组不同的位长。如果将 A 和 B 组合起来，则得到长度：A-2、B-2、C-2 和 D-2。如果你把 C+D 和 B 结合起来，你会得到 A-1、B-2、C-3、D-3。两者都是最佳代码，因为 2x2 + 2x2 + 1x2 + 1x2 = 2x1 + 2x2 + 1x3 + 1x3 = 12，所以两个代码都使用 12 位来表示这些符号多次。