霍夫曼编码如何计算出代码唯一的 属性
How Huffman coding figured out the property that the codes are unique
我刚读完this:
This is where a really smart idea called Huffman coding comes in! The idea is that we represent our characters (like a, b, c, d, ….) with codes like
a: 00
b: 010
c: 011
d: 1000
e: 1001
f: 1010
g: 1011
h: 1111
If you look at these carefully, you’ll notice something special! It’s that none of these codes is a prefix of any other code. So if we write down 010001001011 we can see that it’s 010 00 1001 011 or baec! There wasn’t any ambiguity, because 0 and 01 and 0100 don’t mean anything.
我明白了这个的要点，但我不明白 (a) 它是如何计算出来的，以及 (b) 你是如何知道它是如何工作的，或者 (c) 它到底是什么意思。具体这一行是这样描述的：
So if we write down 010001001011 we can see that it’s 010 00 1001 011....
我看到那些是代码，但我不明白你怎么知道不要把它读成0100 01 0010 11。我看到这些值实际上并不是 table 中的代码。但是，我不明白你是怎么想出来的！我想知道如何发现这一点。如果我想像这样修改代码和位，我会这样做：
- 想出一组代码，比如
10 100 1000 101 1001
- 尝试编写一些代码示例。所以也许一个例子只是按上面的顺序连接代码：
1010010001011001.
- 看看我能不能解析代码。所以
10 或者哎呀，不 101 也... Darnit，好吧也许我可以 添加一个优先级 到代码的解析中，所以 10 的优先级高于 101。这让我 10 100 1000 10 x 不，最后 10 个应该是 101。Dangit。
所以我会尝试添加不同的功能，比如那个优先级函数，或者其他我现在想不到的东西，看看它是否有助于解决问题。
我无法想象他们怎么会弄清楚哈夫曼编码中的这些代码可以被唯一解析（我仍然没有看到它，它实际上是如何真实的，我必须写一些例子才能看到它，或者，...这是问题的一部分，如何看到它是真的，如何证明它）。想知道是否有人可以更深入地解释它是如何被证明有效的，以及它是如何被发现的（或者如何自己发现类似的东西）。
霍夫曼代码通过在树中布置数据来工作。如果你有一棵二叉树，你可以通过说左 child 对应于 0 和右 child 对应于 1 的位来将每个叶子关联到一个代码。从根到 a 的路径leaf对应一个code，没有歧义。
这适用于任何树，前缀 属性 是基于叶子是终端的事实。因此，您不能通过另一片叶子（通过将另一个代码作为前缀）转到叶子（获得代码）。
霍夫曼编码的基本思想是，您可以构建树，使每个节点的深度与节点出现的概率相关（更可能发生的代码将更靠近根）。
有几种算法可以构建这样的树。例如，假设您有一组要编码的项目，比如 a..f。由于源模型或实际值分析（例如通过分析文件编码），您必须知道每个项目出现的概率。
那么您可以：
- 按概率对项目排序
- 拾取概率最低的两个物品
- 删除这些项目，将它们分组到一个新的复合节点中，并将一个项目分配给左侧 child（代码 0），另一个分配给右侧 child（代码 1）。
- 复合节点的概率是各个概率的总和，将这个新节点插入到已排序的项目列表中。
- 当项目数 >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
因此前缀 属性 由构造保险。
我刚读完this:
This is where a really smart idea called Huffman coding comes in! The idea is that we represent our characters (like a, b, c, d, ….) with codes like
a: 00 b: 010 c: 011 d: 1000 e: 1001 f: 1010 g: 1011 h: 1111If you look at these carefully, you’ll notice something special! It’s that none of these codes is a prefix of any other code. So if we write down
010001001011we can see that it’s010 00 1001 011orbaec! There wasn’t any ambiguity, because0and01and0100don’t mean anything.
我明白了这个的要点，但我不明白 (a) 它是如何计算出来的，以及 (b) 你是如何知道它是如何工作的，或者 (c) 它到底是什么意思。具体这一行是这样描述的：
So if we write down
010001001011we can see that it’s010 00 1001 011....
我看到那些是代码，但我不明白你怎么知道不要把它读成0100 01 0010 11。我看到这些值实际上并不是 table 中的代码。但是，我不明白你是怎么想出来的！我想知道如何发现这一点。如果我想像这样修改代码和位，我会这样做：
- 想出一组代码，比如
10 100 1000 101 1001 - 尝试编写一些代码示例。所以也许一个例子只是按上面的顺序连接代码：
1010010001011001. - 看看我能不能解析代码。所以
10或者哎呀，不101也... Darnit，好吧也许我可以 添加一个优先级 到代码的解析中，所以10的优先级高于101。这让我10 100 1000 10 x不，最后 10 个应该是 101。Dangit。
所以我会尝试添加不同的功能，比如那个优先级函数，或者其他我现在想不到的东西，看看它是否有助于解决问题。
我无法想象他们怎么会弄清楚哈夫曼编码中的这些代码可以被唯一解析（我仍然没有看到它，它实际上是如何真实的，我必须写一些例子才能看到它，或者，...这是问题的一部分，如何看到它是真的，如何证明它）。想知道是否有人可以更深入地解释它是如何被证明有效的，以及它是如何被发现的（或者如何自己发现类似的东西）。
霍夫曼代码通过在树中布置数据来工作。如果你有一棵二叉树，你可以通过说左 child 对应于 0 和右 child 对应于 1 的位来将每个叶子关联到一个代码。从根到 a 的路径leaf对应一个code，没有歧义。
这适用于任何树，前缀 属性 是基于叶子是终端的事实。因此，您不能通过另一片叶子（通过将另一个代码作为前缀）转到叶子（获得代码）。
霍夫曼编码的基本思想是，您可以构建树，使每个节点的深度与节点出现的概率相关（更可能发生的代码将更靠近根）。
有几种算法可以构建这样的树。例如，假设您有一组要编码的项目，比如 a..f。由于源模型或实际值分析（例如通过分析文件编码），您必须知道每个项目出现的概率。
那么您可以：
- 按概率对项目排序
- 拾取概率最低的两个物品
- 删除这些项目，将它们分组到一个新的复合节点中，并将一个项目分配给左侧 child（代码 0），另一个分配给右侧 child（代码 1）。
- 复合节点的概率是各个概率的总和，将这个新节点插入到已排序的项目列表中。
- 当项目数 >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
因此前缀 属性 由构造保险。