该霍夫曼表是如何创建的? [英] How is this Huffman Table created?

问题描述

我有一张表，显示事件发生的可能性. 我对第1部分没问题，但第2部分没有跟我一起点击.我正在努力弄清楚如何 二进制数是在第2部分中得出的?

I have a table that shows the probability of an event happening. I'm fine with part 1, but part 2 is not clicking with me. I'm trying to get my head around how the binary numbers are derived in part 2?

我知道0被分配给最大概率，我们从那里开始计算，但是我们如何算出下一组二进制数是什么呢?数字周围的圆圈表示2个灰色阴影有什么区别?

I understand 0 is assigned to the largest probability and we work back from there, but how do we work out what the next set of binary numbers is? And what do the circles around the numbers mean/2 shades of grey differentiate?

只是没有点击.也许有人可以用一种能让我理解的方式来解释它?

It's just not clicking. Maybe someone can explain it in a way that will make me understand?

推荐答案

要构建霍夫曼代码，一种方法是使用优先级队列构建二叉树，在该树中插入要分配的代码数据，并按频率排序

To build huffman codes, one approach is to build a binary tree, using a priority queue, in which the data to be assigned codes are inserted, sorted by frequency.

首先，您有一个只有叶节点的队列，代表每个数据.

To start with, you have a queue with only leaf nodes, representing each of your data.

在每个步骤中，从队列中取出两个优先级最低的节点，创建一个频率等于两个已删除节点之和的频率的新节点，然后将这两个节点作为左子节点和右子节点附加.该新节点将根据其频率重新插入队列.

At each step you take the two lowest priority nodes from the queue, make a new node with a frequency equal to the sum of the two removed nodes, and then attach those two nodes as the left and right children. This new node is reinserted into the queue, according to it's frequency.

重复此操作，直到队列中只有一个节点(它将是根节点)为止.

You repeat this until you only have one node in the queue, which will be the root.

现在，您可以将树从根遍历到任何叶节点，并且在每个级别上采用的路径(无论是向左还是向右)为您提供0或1，以及路径的长度(如何节点所在的树的下方)为您提供了代码的长度.

Now you can traverse the tree from the root to any leaf node, and the path you take (whether you go left or right) at each level gives you either a 0 or a 1, and the length of the path (how far down the tree the node is) gives you the length of the code.

在实践中，您可以仅在构建树时构建此代码，但根据是将其所属的子树添加到树的左侧还是右侧，将0或1附加到每个节点的代码上.一些新的父母.

In practice you can just build this code as you build the tree, but appending 0 or 1 to the code at each node, according to whether the sub-tree it is part of is being added to the left or the right of some new parent.

在图中，圆圈中的数字表示在构建树的每个阶段组合的两个节点的频率之和.

In your diagram, the numbers in the circles are indicating the sum of the frequency of the two nodes which have been combined at each stage of building the tree.

您还应该看到组合在一起的两个分配了不同的位(一个为0，另一个为1).

You should also see that the two being combined have been assigned different bits (one a 0, the other a 1).

图表可能会有所帮助.为我的手写道歉:

A diagram may help. Apologies for my hand-writing:

这篇关于该霍夫曼表是如何创建的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！