encoding - 霍夫曼编码如何找出代码唯一的属性

Question

我刚刚读过这个：

这就是一个叫做霍夫曼编码的非常聪明的想法出现的地方！这个想法是我们用如下代码表示我们的字符（如a，b，c，d，......）

a: 00
b: 010
c: 011
d: 1000
e: 1001
f: 1010
g: 1011
h: 1111

如果你仔细看这些，你会发现一些特别的东西！就是这些代码都不是任何其他代码的前缀。因此，如果我们写下来，010001001011我们可以看到它是010 00 1001 011or baec！没有任何歧义，因为and0没有任何意义。010100

我明白了这一点，但我不明白（a）它是如何计算出来的，以及（b）你是如何知道它工作的，或者（c）它的确切含义。具体来说，这一行描述了它：

所以如果我们写下来，010001001011我们可以看到它是010 00 1001 011......

我看到这些是代码，但我不明白你怎么知道不把它读成0100 01 0010 11. 我看到这些值实际上并不是表中的代码。但是，我不知道您将如何解决这个问题！我想知道如何发现这一点。如果我试图修改这样的代码和位，我会这样做：

1. 想出一组代码，比如10 100 1000 101 1001
2. 试着写出一些代码示例。所以也许一个例子只是按照上面的顺序连接代码：1010010001011001.
3. 看看我是否可以解析代码。So 10or oops, 101nope also... Darnit，也许我可以为代码的解析添加一个优先级，所以10优先级高于101. 这让我10 100 1000 10 x不以为然，最后 10 名应该是 101。Dangit。

所以我会尝试添加不同的功能，比如优先功能，或者其他我现在想不到的东西，看看它是否有助于解决问题。

我无法想象他们如何弄清楚霍夫曼编码中的这些代码可以被唯一解析（我仍然没有看到它，它实际上是如何真实的，我必须写一些例子才能看到它，或者，. ..这是问题的一部分，如何看到它是真的，如何证明它）。想知道是否可以更深入地解释它是如何被证明有效的，以及它是如何被发现的（或者如何自己发现类似的东西）。

标签： encodingcompressionbit-manipulationhuffman-code

Answer 1

霍夫曼代码通过在树中布置数据来工作。如果你有一棵二叉树，你可以通过说左子对应于 0 的位，右子对应于 1 来将每个叶子与代码相关联。从根到叶子的路径对应于非模棱两可的方式。

这适用于任何树，并且前缀属性基于叶子是终端的事实。因此，您不能通过传递另一个叶子（通过让另一个代码作为前缀）进入叶子（有一个代码）。

霍夫曼编码的基本思想是，您可以构建树，使每个节点的深度与节点出现的概率相关（更有可能发生的代码将更接近根）。

有几种算法可以构建这样的树。例如，假设您有一组要编码的项目，例如 a..f。您必须知道每个项目的出现概率，这要归功于源模型或对实际值的分析（例如通过分析文件到代码）。

那么你就可以：

1. 按概率对项目进行排序
2. 捡起概率最低的两件物品
3. 删除这些项目，将它们分组到一个新的复合节点中，并将一个项目分配给左孩子（代码 0），将另一个项目分配给右孩子（代码 1）。
4. 复合节点的概率是各个概率的总和，并将这个新节点插入到排序的项目列表中。
5. 当项目数> 1时转到2

对于之前的树，它可能对应一组概率

a (0.5) b (0.2) c (0.1) d (0.05) e (0.05) f (0.1)

然后选择概率最低的项目（d 和 e），将它们分组到复合节点（de）中并获得新列表

a (0.5) b (0.2) c (0.1) (de) (0.1) f (0.1)

并且连续的项目列表可以是

a (0.5) b (0.2) c(de) (0.2) f (0.1)

a (0.5) b (0.2) (c(de))f (0.3)

a (0.5) b((c(de))f) (0.5)

a(b(((c(de))f)) 1.0

所以前缀属性是由建筑投保的。